地震逃生

题目描述

汶川地震发生时,四川\*\*中学正在上课,一看地震发生,老师们立刻带领 $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$ 名学生。

输出格式


两个整数,分别表示每批最多能运出多少个学生,$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$。