A2926. 地震逃生
编程题
提高+/省选-
知识点
题目描述
汶川地震发生时，四川\*\*中学正在上课，一看地震发生，老师们立刻带领 $x$ 名学生逃跑，整个学校可以抽象地看成一个有向图，图中有 $n$ 个点，$m$ 条边。$1$ 号点为教室，$n$ 号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生，只有第一批学生全部逃生完毕后，第二批学生才能从 $1$ 号点出发逃生，现在请你帮校长算算，每批最多能运出多少个学生，$x$ 名学生分几批才能运完。
输入格式
第一行三个整数 $n,m,x$；
以下 $m$ 行，每行三个整数 $a,b,c$（$1\leq a,b\leq n$，$0\leq c\leq x$）描述一条边，分别代表从 $a$ 点到 $b$ 点有一条边，且可容纳 $c$ 名学生。
以下 $m$ 行，每行三个整数 $a,b,c$（$1\leq a,b\leq n$，$0\leq c\leq x$）描述一条边，分别代表从 $a$ 点到 $b$ 点有一条边，且可容纳 $c$ 名学生。
输出格式
两个整数，分别表示每批最多能运出多少个学生，$x$ 名学生分几批才能运完。如果无法到达目的地（$n$ 号点）则输出
Orz Ni Jinan Saint Cow!。输入输出样例
输入 #1
6 7 7 1 2 1 1 4 2 2 3 1 4 5 1 4 3 1 3 6 2 5 6 1
输出 #1
3 3
说明/提示
**【注释】**
比如有图
```plain
1 2 100
2 3 1
```
$100$ 个学生先冲到 $2$ 号点，然后一个一个慢慢沿 $2 \to 3$ 边走过去。
18 神牛规定这样是不可以的……
也就是说，每批学生必须同时从起点出发，并且同时到达终点。
**【数据范围】**
对于 $100 \%$ 的数据，$0 \le x < 2^{31}$，$1 \le n \le 200$，$1 \le m \le 2000$。
比如有图
```plain
1 2 100
2 3 1
```
$100$ 个学生先冲到 $2$ 号点，然后一个一个慢慢沿 $2 \to 3$ 边走过去。
18 神牛规定这样是不可以的……
也就是说，每批学生必须同时从起点出发，并且同时到达终点。
**【数据范围】**
对于 $100 \%$ 的数据，$0 \le x < 2^{31}$，$1 \le n \le 200$，$1 \le m \le 2000$。