オリンピックバス(Olympic Bus)

JOI 国にはN 個の都市があり,1 からN までの番号が付いている.また,都市と都市を一方向に結ぶM
本のバス路線があり,1 からM までの番号が付いている.バス路線i (1 ≦i ≦M) は都市Ui から都市Vi へ
向けて運行されており,運賃はCi 円である.バス路線i (1 ≦i ≦M) では,都市Ui 以外で乗ったり,都市
Vi 以外で降りることはできない.ある都市からある都市へ向けて運行されるバス路線が複数存在するかも
しれない.
JOI 国では間もなくオリンピックが開催される.JOI 国の運輸大臣であるK 理事長は,バス路線を高々1
つ選び,オリンピック期間中,運賃を変更せずにそのバス路線の運行方向を反転させることにした.つま
り,バス路線i (1 ≦i ≦M) を選んだ場合,オリンピック期間中,そのバス路線は都市Ui から都市Vi へ向
けて運行されるのではなく,都市Vi から都市Ui へ向けて運行されるようになる.ただし,バス路線i の
運行方向の反転にはDi 円かかり,これはK 理事長のポケットマネーにより賄われる.また,混乱を避け
るため,オリンピック期間の途中でバス路線を反転させることはできない.
運輸大臣であるK 理事長は,オリンピック期間中,都市1 と都市N の間をバス路線を乗り継いで往復
する予定である.運行方向を反転させるバス路線をうまく選ぶことで,往復の合計運賃と運行方向の反転
の費用との和を最小化したい.
都市の個数と,バス路線の情報が与えられたとき,運行方向を反転させるバス路線をうまく選ぶことで,
都市1 と都市N の間の往復の合計運賃と,運行方向の反転の費用との和の最小値を求めるプログラムを作
成せよ.ただし,どのようにバス路線を選んでも都市1 と都市N の間を往復することができない場合は,
代わりに−1 を出力せよ.

• 2 ≦N ≦200.
• 1 ≦M ≦50 000.
• 1 ≦Ui ≦N (1 ≦i ≦M).
• 1 ≦Vi ≦N (1 ≦i ≦M).
• Ui , Vi (1 ≦i ≦M).
• 0 ≦Ci ≦1 000 000 (1 ≦i ≦M).
• 0 ≦Di ≦1 000 000 000 (1 ≦i ≦M).

1. (5 点) M ≦1000.
2. (11 点) M は偶数,U2i−1 = U2i,V2i−1 = V2i,C2i−1 = C2i (1 ≦i ≦M
   2 ).
3. (21 点) Ci = 0 (1 ≦i ≦M).
4. (63 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M
U1 V1 C1 D1
...
UM VM CM DM

都市1 と都市N の間の往復の合計運賃と,運行方向の反転の費用との和の最小値を,標準出力に1 行で
出力せよ.ただし,どのようにバス路線を選んでも都市1 と都市N の間を往復することができない場合は,
代わりに−1 を出力せよ.

第19 回日本情報オリンピック(JOI 2019/2020) 本選
2020 年2 月9 日(茨城県つくば市)

생성자가 기록되지 않았습니다.

출처 JOI 2020 Final