0604 - Hina's Christmas

時間制限 1 秒 / メモリ制限 64 MB / 得点 10 / Writer root / x 5 / 統計 /


TLE
1sec
MLE
64MB
得点
10

問題

     ,、ィyァ,、
    ァ,' (ノリ))ヽ
    ノリ,!*・ω・ヾヽ  ひなぽ
    (_{    厄}   メリークリスマス!!
     `'ー-- -‐´

幻想郷にもクリスマスがやってきた!!

さて、我らが鍵山雛ちゃんだが、見た目がサンタのようである!!

さて雛ちゃんには、大親友のパルスィさんがいる!!

雛ちゃんはパルスィさんに、

クリスマスプレゼントとして厄をプレゼントしようとしている!!

いい迷惑である!!

さて、雛ちゃんは厄を雛ちゃん独自の厄パイプラインを用いて渡そうとしている!!

厄は、雛ちゃんの家を出発して最終的には

パルスィさんの家に届くようにしたい!!

パイプラインは、ある二つの中継地点を繋いでいる!!

このパイプラインは、当然だが一方向にしか厄を流すことは出来ない!!

さて、厄の中継地点の数とパイプラインの数と各パイプラインの情報、

更に雛ちゃんがパルスィさんに渡したい厄の総量が与えられるので、

雛ちゃんが一分間にパルスィさんに渡すことの出来る厄の量、

渡したい分の厄が渡されるまでの時間(分単位)を出力せよ!!

入力形式

一行目に、厄の中継地点の数 N 、パイプラインの数 M

渡したい厄の総量 Y が一行に与えられる。

中継地点には、雛ちゃんの家とパルスィさんの家も含まれる。

二行目から、M行にかけて、パイプラインの始点 A と終点 B

一分間に流せる最大の厄の量 C が与えられる。

なお、雛ちゃんの家の番号は 0 、パルスィさんの家の番号は N-1 である。

出力形式

雛ちゃんが一分間にパルスィさんの家に流すことの出来る最大の厄の量、

渡したいだけの厄を渡すまでにかかる時間(分単位)を一行に出力せよ。

もしもいつまで経っても厄を渡しきることができない、

つまり厄を一切流すことが出来ない場合は、"Accident"を出力せよ。

制約

  • 0 ≦ A,B < N ≦ 100
  • 0 ≦ M ≦ 1,000
  • 0 ≦ Y,C ≦ 891,891,891

入出力例

入力例壱

4 5 8
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2

出力例壱

3
3

この場合一分間に流せる最大の厄の量は3であり、

厄を8流すには3分必要である。

入力例弐

6 9 231
0 1 1
0 2 12
1 3 2
2 1 6
2 3 5
2 4 7
3 4 10
3 5 3
4 5 12

出力例弐

13
18

入力例参

2 1 3
0 1 0

出力例参

0
Accident