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?

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).

提交代码