Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2281
Way to Freedom

Time Limit: 2 Seconds      Memory Limit: 32768 KB

Background

"Now, you are getting closer and closer to Your Gate to Freedom!

And you will pass the most dangerous paths! Be careful!"

We're in a maze now. There're many rooms floating in the sky connected with wooden bridges. Bridges seems unstable...


Problem

At first, I'm in room X, and I want to go to room Y. There're N (N <= 100,000) rooms connected with M (M <= 1,000,000) edges. Each edge has a limit of weight, if weight exceeds this value, the edge will split, and drop me into the river.

How many things I can take to room Y at most?


Input

This problem contains multiple test cases.

Each test case begins with two integers N and M, then M lines, each line has 3 numbers: X, Y and Weight (<=2,000,000,000).


Output

For each test case, output the maximum weight I can take.


Sample Input

6 6
1 5 2000
2 4 5000
2 5 3300
3 4 2400
3 6 2200
4 6 6000
3 5


Sample Output

2400


Contest: A Great Beloved and My Gate to Freedom
There is a cx, there is a love_cx.


Author: JIANG, Yanyan
Source: JIANG, Yanyan's Contest #2
Submit    Status