F - Road Construction
Editorial
/


Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
1 から N の番号が付いた N 個の都市があります。 最初、これらの都市の間に道路はありません。
道路の建設案が M 個あり、i 番目の案は、費用 c_i 円で都市 s_i から都市 t_i (s_i \lt t_i) へ一方通行の道路を建設するというものです。
このうちのいくつかを採用して、都市 w から都市 x、都市 y から都市 z がそれぞれ通行可能となるようにしたいです。
上の条件を満たすのに必要な金額の最小値を求めてください。
制約
- 入力は全て整数
- 4 \leq N \leq 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq w \lt x \leq N
- 1 \leq y \lt z \leq N
- 1 \leq c_i \leq 10^9
- 1 \leq s_i \lt t_i \leq N
- w, x, y, z はそれぞれ相異なる
- i \ne j のとき (s_i, t_i) \ne (s_j, t_j)
入力
入力は以下の形式で標準入力から与えられる。
N M w x y z c_1 s_1 t_1 \vdots c_{M} s_{M} t_{M}
出力
都市 w から都市 x、都市 y から都市 z をそれぞれ通行可能とす る最小の費用を出力してください。
そのような建設案の選び方が存在しない場合、代わりに Impossible
を出力してください。
入力例 1
5 6 2 5 1 4 1 3 5 3 2 5 1 1 2 1 3 4 4 1 4 3 2 3
出力例 1
6
- 建設案 1, 3, 4, 6 を採用することで総費用は 6 円となり、これが最小です。
入力例 2
5 5 1 3 2 5 4 2 3 2 2 4 5 3 5 1 1 4 3 4 5
出力例 2
Impossible
- どのように建設案を選んでも、指定された都市間が通行可能となることはありません。
入力例 3
5 8 1 3 2 5 42 2 3 32 2 4 12 3 5 94 1 4 21 4 5 79 1 2 22 1 5 90 1 3
出力例 3
133