Welcome to ZOJ
131 - ZOJ Monthly, March 2014 - H
New Governor's Problem

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Recently the new governor KT encountered a hard problem. Her province has N major cities, and there are many old roads connects pairs of cities. Each road has a traffic volume. Because of the bucket theory, when going from one city to another through a route consisting of some roads, the maximum total traffic volume is the minimal traffic volume of one road in the route. From one city to another city, you can choose more than one route, but at any time, a road's transport volume can not exceed its maximal transport volume.

Because of the province's industrial restructuring, some of the roads are not so important as before. In order to reduce the cost of the government management, she wants to close at most K roads. But there are two big cities numbered 1 and N in the province. And between these two cities there is a traffic demand. Her adviser told her that no matter which roads she chooses to close, the impact on the transport volume is small. But smart KT does not believe what he said.

To prove that, she want you to calculate that, at the worst case after she closing some roads, the minimum transport volume from city 1 to city N.


There are multiple test cases. For each test case:

The first line contains three integer N(1≤N≤10), M(1≤M≤1000), K(0≤K≤M), N is the number of cities, M is the number of roads, please notice that the roads is bidirectional, and K has mentioned above.

The after M lines describe the roads, each line has three integers A, B(1≤A,BN), C(1≤C≤108). That means the transport volume from city A to city B is C.

There is a blank line between every two cases.

Process to the end of input.


One line for each test case. The minimum traffic volume from city 1 to city N after she closing at most K roads.

Sample Input

2 1 0
1 2 1

2 2 1
1 2 1
1 2 2

Sample Output


Author: TANG, Yajie
Submit    Status