F - Road Construction

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