問題文

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

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

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

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

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

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

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

制約

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

小課題

1. (7 点) M = N - 1，(A_i, B_i) = (i, i + 1) または (A_i, B_i) = (i + 1, i) (1 \leqq i \leqq M)．
2. (14 点) M は偶数，A_{2i - 1} = B_{2i}，A_{2i} = B_{2i - 1}，C_{2i - 1} = C_{2i} (1 \leqq i \leqq \frac M 2)．
3. (18 点) N \leqq 15，M \leqq 15．
4. (20 点) C_i = 1 (1\leqq i \leqq M)，L = 1\,000\,000\,000．
5. (20 点) C_i = 1 (1\leqq i \leqq M)．
6. (21 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

3 2 5
2 1 2
2 3 3

出力例 1

1

道 1 の進行方向を反転させると，パレードを行うことができる．

これが最小値であるため，1 を出力する．

この入力例は小課題 1,3,6 の制約を満たす．

入力例 2

3 1 10
2 1 5

出力例 2

-1

どのように道の進行方向を反転させてもパレードを行うことができないため，-1 を出力する．

この入力例は小課題 3,6 の制約を満たす．

入力例 3

4 8 11
3 1 6
1 3 6
2 4 3
4 2 3
4 3 6
3 4 6
2 1 5
1 2 5

出力例 3

0

この入力例は小課題 2,3,6 の制約を満たす．

入力例 4

5 6 1000000000
5 2 1
2 3 1
3 4 1
4 2 1
2 1 1
1 3 1

出力例 4

1

この入力例は小課題 3,4,5,6 の制約を満たす．

入力例 5

6 15 777777
1 3 497295
4 1 422722
4 5 607164
2 3 135688
5 2 995652
5 1 670296
3 1 138860
4 6 736614
6 3 620085
2 1 796353
6 4 949756
4 2 750680
6 5 591550
5 3 229431
3 2 668173

出力例 5

2

この入力例は小課題 3,6 の制約を満たす．