There are multiple test cases in the input file. Each test case starts with three integers N , M and D , (2<=N<=300, 1<=M<=3000) , the number of intersections, the number of edges, and the range of each EMP charge, respectively. Intersections are numbered from 0 to N - 1 . The following line consists of N integers, the cost of deploying an EMP charge on intersection i . The next M lines each consists of three integers S , T , and C , (0<=S, T<=N - 1, 1<=C<=20000) , meaning that intersection S and T are connected by a tunnel whose length is C . Every test case ends with one blank line indicating the end of test case.
N = 0 , M = 0 , D = 0 indicates the end of input file and should not be processed by your system.