{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThe 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)\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases, please process till EOF.\u003cbr\u003eThe first line of each test case contains three integer N(2 \u0026lt;\u003d N \u0026lt;\u003d 2500), M(0 \u0026lt;\u003d M \u0026lt;\u003d 5000), K(0 \u0026lt;\u003d K \u0026lt;\u003d 10\u003csup\u003e9\u003c/sup\u003e). Then follows M lines, each line has three numbers a\u003csub\u003ei\u003c/sub\u003e, b\u003csub\u003ei\u003c/sub\u003e, c\u003csub\u003ei\u003c/sub\u003e(0 \u0026lt;\u003d c\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 20), means there is an edge from vertex a\u003csub\u003ei\u003c/sub\u003e to b\u003csub\u003ei\u003c/sub\u003e with the capacity c\u003csub\u003ei\u003c/sub\u003e."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print an integer represents the minimum time. If the requirements can not be met, print “No solution”(without quotes) instead."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6 4\r\n0 1 2\r\n0 3 1\r\n1 2 1\r\n2 3 1\r\n1 4 1\r\n3 4 2\r\n3 3 10\r\n0 1 1\r\n1 2 1\r\n0 2 1\r\n2 0 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n6\r\nNo solution\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}