Olympiads
Por 
Brazil
Por Brazil
Tumbolia is a small country in eastern South America (or southern South America) that will participate in the Olympic Games for the first time in its history. Although its delegation is very small compared to the total number of athletes who will be in Beijing (official estimates are more than 10,000 athletes), participation will be key to the image and tourism of Tumbolia. After selecting the athletes, the Tumbol Olympic Committee (TOC) must buy tickets for them. In order to save money, TOC decided to buy only Air Rock tickets. However, many of Air Rock's tickets have already been sold, as many of the fans of the game want to watch the Games. Therefore, the TOC must buy tickets according to the vacant seats on each flight. All Air Rock flights depart daily before noon and arrive after noon; so an athlete can only take one plane per day. Air Rock has provided a list containing all the flights operated by it and the number of seats vacant in each one (curiously, the number of free seats in the same stretch is the same every day). The TOC has verified that it is really possible to go from Tumbolia to Beijing using only Air Rock flights, but even so, TOC is having difficulty planning the trip for its athletes. That's why the TOC has asked you to write a program that, given Air Rock's list of flights, determines the least amount of days it takes for all athletes to arrive in Beijing.
The input contains many test cases. The first line of each test case contains three integers N, M, and A, respectively indicating the number of airports in which Air Rock operates (2 ≤ N ≤ 50), the number of flights where there are vacant seats (1 ≤ M ≤ 2.450) and how many athletes the delegation of Tumbolia has (1 ≤ A ≤ 50). Eahch of the M next lines contains a description of fly with three integers O, D and S which indicate respectively the airport of origin (1 ≤ O ≤ N), the destination airport (1 ≤ D ≤ N and O 6= D) and the number of vacant seats that fly (1 ≤ S ≤ 50). The airports are numbereds from 1 to N; The intenational airport of Tumbolia is the airport 1, and de international airport of Beijing is the airport N. The existence of a flight from A to B does not implies the existence of a flight of B to A (but there is always a maximum of one flight from one airport to another in each direction). The final of input is indicated to N = M = A = 0.
For each entrance test case your program should produce an output line containing an integer, indicating the minimum number of days required for all Tumbolian athletes to arrive in Beijing (some athletes may arrive after others, and they do not need to arrive at same order in which they left).
| Input Sample | Output Sample |
|
3 3 3 1 2 2 2 3 2 1 3 1 3 3 5 1 2 1 2 3 5 3 1 4 4 4 4 1 4 1 1 2 1 2 3 1 3 4 1 0 0 0 |
2 6 3 |