Telephone Line Repair

After a major earthquake, the telephone network in a city has been damaged. There are N telephone poles numbered from 1 to N scattered around the city, and P possible pairs of poles that can be connected with a cable (only these pairs can be connected). Pole 1 is already connected to the nationwide telephone network, and pole N is located in the disaster area. The task is to connect pole 1 to pole N using a sequence of cables.

The phone company agrees to provide k cables for free. For all other cables that must be used, Farmer John (now the telephone line engineer) has to pay a fee equal to the length of the longest cable among those he pays for. In other words, if he uses more than k cables, he can choose exactly k cables to be free, and he must pay an amount equal to the maximum length among the remaining cables. If the total number of cables used does not exceed k, then no payment is required.

Your task is to help him minimize the amount he must pay in order to connect pole 1 to pole N.

Note: If it is possible to connect the two poles with at most k cables, then the answer will be 0.

The problem can be solved using a binary search on the answer combined with a 0-1 cost shortest path algorithm. For any candidate answer X, you can consider each cable having cost 0 if its length is ≤ X and cost 1 otherwise. Then check if there is a route from 1 to N which uses at most k cables with cost 1.

Constraints:

• 1 ≤ N ≤ 1000
• 1 ≤ P ≤ 10000
• 1 ≤ cable length ≤ 1,000,000
• 0 ≤ k < N

inputFormat

The first line contains three integers: N, P and k.

Each of the next P lines contains three integers a_i, b_i and l_i, representing that poles a_i and b_i can be connected by a cable of length l_i.

It is guaranteed that each pair (a_i, b_i) appears at most once. Poles are numbered 1 through N, pole 1 is connected to the phone network, and pole N is at the disaster site.

outputFormat

Output a single integer — the minimum fee that must be paid. If no payment is necessary, output 0.

sample

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

5