#4669. 抢夺

内存限制:256 MiB 时间限制:10 Sec

题目描述

大战将至, 美国决定实行计划经济。美国西部总共有 N 个城市,编号
为 0 ∼ N − 1,以及 M 条道路,道路是单向的。其中城市 0 是一个大城
市,里面住着 K 个人,而城市 N − 1 是一个农业城市。现在所有城市 0 的
居民都需要到城市 N − 1 去领取食物。由于担心体力不支,所以居民都会
采取开车的形式出行。但道路不是无限宽的,对于一条道路,会有 ci 的限
制,表示在同一天内,最多只能有 ci 辆车同时在这条道路上行驶。一条道
路的长度为 1,每辆车的行驶速度也可以假定为 1 每天。城市 N − 1 会在
每个居民都到达后马上开始发放食物。现在 Reddington 想知道,假如在最
优安排下,居民最早能在多少天后领到食物。假如没有居民那就不需要发
放食物,默认为第 0 天。

输入格式

一个测试点包含多组数据。
对于每组数据:
第一行包括三个整数 N, M, K。
接下来 M 行,每行三个整数 u, v, c,描述一条从 u 出发到 v 的道路。
1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 0 ≤ K ≤10^9
0 ≤ u, v < N, 1 ≤ ci ≤ 109,数据组数不超过 10 组

输出格式

对于每组数据,
假如无解,输出”No solution”,不包括引号。
假如有解,输出最早的天数。

样例

样例输入


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

样例输出


			
3
//第 1, 2 个人都选择第 0 天开始出发,分别走 0-1-4, 0-3-4 的道路,第
3,4 个人从第 1 天开始出发,沿着前两个人的路线走。总共只需要 3 天。可
以证明这是最优解。

数据范围与提示