日本情報オリンピック 第1回 女性部門

2021年4月27日
情報オリンピック日本委員会

問題文

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 が与えられたとき，いくつかの道の進行方向を反転させることでパレードを行うことができるかを判定し，もし行うことができる場合はパレードを行うために必要な進行方向を反転させる道の本数の最小値を出力せよ．

制約

• 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)．
• 入力される値はすべて整数である．

小課題

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

採点に関する注意

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

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

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

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

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

入力

入力は以下の形式で標準入力から与えられる．
N M L
A₁ B₁ C₁
A₂ B₂ C₂
:
A_M B_M C_M

出力

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

入出力例

入力例 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 の制約を満たす．