Lunch Time

The campus of Nanjing University of Science and Technology can be viewed as a graph with N vertexes and M directed edges (vertexes are numbered from 0 to N - 1). Each edge has the same length 1. Every day, there are K students walking to the dinning-hall (vertex N - 1) from the teaching building (vertex 0) at lunch time. They all want reach the dinning-hall as soon as possible. However, each edge can only serve at most ci students at any time. Can you make arrangements for students, so that the last student can reach the dinning-hall as soon as possible? (It is assumed that the speed of the students is 1 edge per unit time)

There are several test cases, please process till EOF.
The first line of each test case contains three integer N(2 <= N <= 2500), M(0 <= M <= 5000), K(0 <= K <= 10⁹). Then follows M lines, each line has three numbers a_i, b_i, c_i(0 <= c_i <= 20), means there is an edge from vertex a_i to b_i with the capacity c_i.

For each test case, print an integer represents the minimum time. If the requirements can not be met, print “No solution”(without quotes) instead.

5 6 4
0 1 2
0 3 1
1 2 1
2 3 1
1 4 1
3 4 2
3 3 10
0 1 1
1 2 1
0 2 1
2 0 1

3
6
No solution

2013ACM/ICPC亚洲区南京站现场赛——题目重现