Problem Description
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)
Input
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 <= 109). Then follows M lines, each line has three numbers ai, bi, ci(0 <= ci <= 20), means there is an edge from vertex ai to bi with the capacity ci.
Output
For each test case, print an integer represents the minimum time. If the requirements can not be met, print “No solution”(without quotes) instead.
Sample Input
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
Sample Output
3
6
No solution
