Spacejump

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

There is a war between Star X and Star Y. As the general of Star X, you need to send your soldiers to Star Y by spaceship. The only way to get there quickly is by doing spacejump through windows built in space (directed). Doing spacejump once costs one unit of source. As the space windows are unstable, there is a factor W, which means no more than W people can pass through the window together. The source for the spaceship is limited, but the number of people carried is unlimited. Since the war has been started for some time, you urge to send more soldiers to Star Y, can you calculate the number of soldiers?

Input

There is a single integer T (0<T<=5) in the first line, indicating the case number. For each case, there are to integers N (0<N<=200) and M (30000<M<=39800), E (50<E<=100), indicating the number of stars, space windows and the amount of source which a spaceship can carry. Following M lines, each line contains three integers U, V, W, meaning there is a space window between Star U and Star V, and stability factor is W. (Promise that Star X is numbered 1, and Star Y is numbered N, the number of spaceship is unlimited).

Output

For each case, print the number of the most soldiers sent to Star Y.

Sample Input

2

5 7 3
1 2 5
1 3 2
2 3 3
2 4 2
4 3 1
3 5 1
4 5 2

5 7 2
1 2 5
1 3 2
2 3 3
2 4 2
4 3 1
3 5 1
4 5 2

Sample Output

3
1

Hint

Source

The First ACM-ICPC Nanjing Invitational Tourn

提交代码