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

Submit

Source: JIANG, Yanyan's Contest #2