Setting

Mr. G. works as a tourist guide in Bangladesh. His current assignment is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus service that runs only between those two cities and uses the road the directly connects them. Each bus service has a particular limit on the maximum number of passengers it can carry. Mr. G. has a map showing the cities and the roads connecting them, as well as the service limit for each bus service.

It is not always possible for him to take all the tourists to the destination city in a single trip. For example, consider seven cities with the following connections between them:

City    City    Passenger limit
-------------------------------
   1       2                 30
   1       3                 15
   1       4                 10
   2       4                 25
   2       5                 60
   3       4                 40
   3       6                 20
   4       7                 35
   5       7                 20
   6       7                 30

It will take at least five trips for Mr. G. to take 99 tourists from city 1 to city 7, since he has to ride the bus with each group (the first four trips will consist of two ways each, the last trip of one way). The best route to take is 1-2-4-7.

Help Mr. H. find the route to take all his tourists to the destination city in the minimum number of trips.

Input

The input will contain one or more test cases. The first line of each test case will contain two integers: \(n\) (\(n \leq 100\)) and \(r\), representing the number of cities and the number of roads, respectively. Each of the next \(r\) lines will contain three integers \(c_1\) (the first city), \(c_2\) (the second city), and \(p\) (the maximum number of passengers that can be carried along that road between the two cities, with \(p > 1\)). City numbers are positive integers ranging from \(1\) to \(n\). The \((r+1)\)th line will contain three integers representing, respectively, the starting city, the destination city, and the number of tourists to be guided.

The input will end with \(n = r = 0\).

Output

For each test case in the input, print the minimum number of trips required for this case on a separate line.

Sample Input

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0

Sample Output

5

This is challenge 10099 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (0 votes)
Average test runtime 0.37
Points (changes over time) 10
Tried by 6 users
Solved by 5 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.21 16
2 JB 0.25 13
3 Mac 0.41 8
4 IeM 0.49 7
5 Dark 0.50 7