AT_ttpc2019_f Road Construction

[problemUrl]: https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_f $ 1 $ から $ N $ の番号が付いた $ N $ 個の都市があります。 最初、これらの都市の間に道路はありません。 道路の建設案が $ M $ 個あり、$ i $ 番目の案は、費用 $ c_i $ 円で都市 $ s_i $ から都市 $ t_i $ $ (s_i\ \lt\ t_i) $ へ一方通行の道路を建設するというものです。 このうちのいくつかを採用して、都市 $ w $ から都市 $ x $、都市 $ y $ から都市 $ z $ がそれぞれ通行可能となるようにしたいです。 上の条件を満たすのに必要な金額の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ w $ $ x $ $ y $ $ z $ $ c_1 $ $ s_1 $ $ t_1 $ $ \vdots $ $ c_{M} $ $ s_{M} $ $ t_{M} $

都市 $ w $ から都市 $ x $、都市 $ y $ から都市 $ z $ をそれぞれ通行可能とす る最小の費用を出力してください。 そのような建設案の選び方が存在しない場合、代わりに `Impossible` を出力してください。

### 制約 - 入力は全て整数 - $ 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) $ ### Sample Explanation 1 \- 建設案 $ 1,\ 3,\ 4,\ 6 $ を採用することで総費用は $ 6 $ 円となり、これが最小です。 !\[\](https://img.atcoder.jp/ttpc2019/788a099ba91f1acd3b107259107edde3.png) ### Sample Explanation 2 \- どのように建設案を選んでも、指定された都市間が通行可能となることはありません。