22019번 - パレード (Parade) 서브태스크다국어

JOI 王国では，JOIG の開催を記念して鼓笛隊のパレードを行うことになった．

JOI 王国には N 個の都市があり，1 から N までの番号が付けられている．また，鼓笛隊が通行可能な一方通行の道が M 本あり，1 から M までの番号が付けられている．道 i (1 ≦ i ≦ M) は都市 A_i から都市 B_i へ向かう一方通行の道であり，長さは C_i である．

パレードでは，鼓笛隊は次の条件を満たすように移動しなければならない．

• 都市 1 を出発し，何本かの道を進行方向に進むことを繰り返して都市 N へ向かう．
• 鼓笛隊が通る道の長さの総和は L 以下である．

JOI 王国の女王であるあなたは，この条件を満たす鼓笛隊の移動経路が無いかもしれないことに気が付いた．そこで，パレードを行うために，パレード当日に 0 本以上の道の進行方向を反転させることにした．

混乱を避けるため，なるべく進行方向を反転させる道の本数は少なくしたい．

JOI 王国の都市と道の情報と，整数 L が与えられたとき，いくつかの道の進行方向を反転させることでパレードを行うことができるかを判定し，もし行うことができる場合はパレードを行うために必要な進行方向を反転させる道の本数の最小値を出力せよ．

入力は以下の形式で標準入力から与えられる．

N M L
A1 B1 C1
A2 B2 C2
:
AM BM CM

標準出力に，パレードを行うために必要な進行方向を反転させる道の本数の最小値を 1 行で出力せよ．ただし，どのように道の進行方向を反転させてもパレードを行うことができない場合は，-1 を出力せよ．

• 2 ≦ N ≦ 1 000．
• 0 ≦ M ≦ 1 000．
• 1 ≦ L ≦ 1 000 000 000．
• 1 ≦ A_i ≦ N (1 ≦ i ≦ M)．
• 1 ≦ B_i ≦ N (1 ≦ i ≦ M)．
• A_i ≠ B_i (1 ≦ i ≦ M)．
• (A_i, B_i) ≠ (A_j, B_j) (1 ≦ i < j ≦ M)．
• 1 ≦ C_i ≦ 1 000 000 (1 ≦ i ≦ M)．
• 入力される値はすべて整数である．