题目描述

Blue Mary 和 $T$ 个同事要从城市 $1$ 到城市 $N$，乘坐 U 航空公司的航班。
每条航班 $(x,y,z)$ 是单向的，且每天最多买 $z$ 张票，每人每天只能乘一班飞机。
目标：安排旅行方案，使得最后到达城市 $N$ 的人到达时间最早。

输入格式

第一行：$N, M, T$（城市数、航班数、人数）
接下来 $M$ 行：$x, y, z$（出发地、目的地、每日最大票数）

输出格式

一个正整数：最后到达的人的最早到达时间

样例

输入

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

输出

6

数据范围与提示

• $2 \le N \le 50$
• $1 \le M \le 2450$
• $1 \le T, z \le 50$
• $1 \le x, y \le N, x \neq y$