汶川地震发生时,四川**中学正在上课,一看地震发生,老师们立刻带领 x 名学生逃跑,整个学校可以抽象地看成一个有向图,图中有 n 个点,m 条边。1 号点为教室,n 号点为安全地带,每条边都只能容纳一定量的学生,超过楼就要倒塌,由于人数太多,校长决定让同学们分成几批逃生,只有第一批学生全部逃生完毕后,第二批学生才能从 1 号点出发逃生,现在请你帮校长算算,每批最多能运出多少个学生,x 名学生分几批才能运完。
第一行 3 个整数 n,m,x(x<231,n≤200,m≤2000);以下 m 行,每行三个整数 a,b,c(1≤a,b≤n,0≤c≤x)描述一条边,分别代表从 a 点到 b 点有一条边,且可容纳c名学生。
两个整数,分别表示每批最多能运出多少个学生, x 名学生分几批才能运完。如果无法到达目的地(n 号点)则输出 Orz Ni Jinan Saint Cow!
汶川地震发生时,四川**中学正在上课,一看地震发生,老师们立刻带领 $x$ 名学生逃跑,整个学校可以抽象地看成一个有向图,图中有 $n$ 个点,$m$ 条边。$1$ 号点为教室,$n$ 号点为安全地带,每条边都只能容纳一定量的学生,超过楼就要倒塌,由于人数太多,校长决定让同学们分成几批逃生,只有第一批学生全部逃生完毕后,第二批学生才能从 $1$ 号点出发逃生,现在请你帮校长算算,每批最多能运出多少个学生,$x$ 名学生分几批才能运完。
## 输入格式
第一行 $3$ 个整数 $n,m,x\;(x<2^{31},n\leq 200,m\leq 2000)$;以下 $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!`