Description

After some time, the network company finally gained some recognition and started receiving orders, the biggest of which came from city B.

Blue Mary decided to personally go and sign this order. To save travel expenses, one of his financial advisors suggested buying tickets only from U Airlines. All flights of U Airlines operate once per day, departing in the morning and arriving in the afternoon of the same day, so each person can take at most one flight per day.

After investigation, they obtained detailed information on all flights operated by U Airlines, including each flight’s origin, destination, and the maximum number of tickets that can be bought for departures on any single day. (Note: For a given flight, the maximum number of tickets they can buy for departures on any day is the same across all days.)

Blue Mary noticed that they can indeed travel from city A to city B using only U Airlines’ flights. However, due to the ticket limits on each flight, it may be impossible for all of them to arrive in city B on the same day.

Therefore, Blue Mary needs your help to design a travel plan that makes the arrival day of the last person to reach city B as early as possible.

Input Format

The first line contains $3$ positive integers $N$, $M$ and $T$.
All cities that appear in the problem are numbered $1, 2, \dots, N$, where city A is numbered $1$, and city B is numbered $N$.
U Airlines has $M$ directed flights in total. Including Blue Mary, the company has $T$ people who need to travel from city A to city B.

The following $M$ lines each contain $3$ positive integers $x, y, z$, indicating the origin, destination, and the maximum number of tickets that Blue Mary can buy for that flight on any given day. (That is, regardless of the day, Blue Mary can buy at most $z$ tickets for the U Airlines flight from city $x$ to city $y$.)

It is guaranteed that between any ordered pair of cities, there is at most one directed flight.

Output Format

Output a single line with one positive integer, the earliest possible day on which the last person arrives in city B. Assume the first day they take a flight is day $1$.

3 3 5
1 2 1
2 3 5
3 1 4

6

Hint

For $100\%$ of the testdata, $2 \le N \le 50$, $1 \le M \le 2450$, $1 \le T, z \le 50$, $1 \le x, y \le N$, $x \ne y$.

Translated by ChatGPT 5