Olympics

Tumbolia is a small country east of South America (or south of East America) and it is sending a delegation to the Olympic Games for the first time in its history. Official estimates put more than ten thousand athletes in Beijing, so the Tumbolian delegation is tiny by comparison, but the trip means a lot for the country's image and for its tourism.

The athletes are selected, so the Tumbolian Olympic Committee now has to buy their tickets. To save money the committee decided to buy tickets from Air Rock only. Many Air Rock seats are already sold, because plenty of Tumbolians want to watch the Games, so the committee can buy only as many tickets as there are free seats on each flight.

Every Air Rock flight leaves before noon and lands after noon, so an athlete can take at most one plane per day. Air Rock gave the committee a list of every flight it operates together with the number of free seats on each one. The number of free seats on a given leg is the same every day. An athlete can stay at an airport for any number of days before taking the next flight.

The committee already confirmed that Beijing is reachable from Tumbolia using Air Rock flights alone. Planning the trip is still hard, so the committee asked for a program that reads the flight list and computes the minimum number of days needed for the whole delegation to reach Beijing.

The input contains several test cases. The first line of each test case has three integers $N$, $M$ and $A$: the number of airports Air Rock serves ($2 \le N \le 50$), the number of flights that still have free seats ($1 \le M \le 2450$), and the number of athletes in the Tumbolian delegation ($1 \le A \le 50$).

Each of the next $M$ lines describes one flight with three integers $O$, $D$ and $S$: the origin airport ($1 \le O \le N$), the destination airport ($1 \le D \le N$, $O \ne D$), and the number of free seats on that flight ($1 \le S \le 50$). Airports are numbered from 1 to $N$. Airport 1 is Tumbolia International and airport $N$ is Beijing International.

A flight from $X$ to $Y$ does not imply a flight from $Y$ to $X$, and there is at most one flight from one airport to another in each direction. A route from airport 1 to airport $N$ always exists.

The end of the input is a line with $N = M = A = 0$. Do not process that line.

For each test case print one line with a single integer, the minimum number of days needed for every Tumbolian athlete to reach Beijing. Count the day the first flights depart as day 1; the answer is the day the last athlete lands. Athletes may land on different days, and they do not have to land in the order they departed.