Batman and Kryptonite

All submissions for this problem are available.
Problem description.
With the help of Harley Quinn, Batman has discovered a new place where he can get Kryptonite to defeat Superman. This new place has N site s(numbered from 0 to N1).There is an entry site(numbered 0) from which every other site is accessible. Batman can get a block of Kryptonite of some specific weight at every site except the entry site. There are paths between sites which take some time to travel. Even though, Batman has trained very hard, he can still carry only one block of Kryptonite at a time. Robin is waiting at the entry gate with the Batmobile ready. What Batman does is, he takes a block of Kryptonite and takes it to his Batmobile and then goes for another block. But, Batman has some specific time before Superman comes and stops him. Batman wants to maximise the amount of Krytonite he can gather in the little time he has. Since, Batman does not have WB excutives to help him, he has asked you to solve this problem for him.
Input
First line contains T ,the number of test cases.
 Second line contains three space seperated integers N, M and D, Number of sites, Number of paths and time Batman has.
 Then follow m lines. Each line will contain three space seperated integers u v e denoting that there is a path from site u and v which take e seconds to travel.
 Last line contains N1 space seperated integer W[i] denoting the weight of kryptonite at the ith site.(1<=i<=N1)
Output
For each test case
 Output the maximum amount of Krytonite he can gather in the given time in a newline.
Constraints
 1 <= T <= 20
 2 <= N <= 10^4
 N1 <= M <= 10^5
 1 <= W[i] <= 10^6
 0 <= u < N
 0 <= v < N
 1 <= e <= 10
 1 <= D <= 1000
Example
Input: 1 7 6 20 0 1 3 0 2 2 2 3 3 0 4 6 4 5 1 5 6 1 1 1 7 1 19 100 Output: 101
Author:  shinigami_ryuk 
Tags  shinigami_ryuk 
Date Added:  12032016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions