AT_nikkei2019_final_f Flights

[problemUrl]: https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_f $ 2 $ 次元平面上に、$ 1 $ から $ N $ までの番号のついた $ N $ 個の国があります。 国 $ i $ は座標 $ (X_i,Y_i) $ にあります。 それぞれの国には航空会社があります。 国 $ i $ の航空会社は、$ X_j\ \leq\ X_i $ かつ $ Y_j\ \leq\ Y_i $ を満たすすべての $ j $ ($ j\ \neq\ i $) について、 国 $ j $ との間に直通便を運航しています。 この直通便は双方向です。 つまり、国 $ i $ の航空会社の飛行機を利用して、国 $ i $ から国 $ j $ へ移動することも、 国 $ j $ から国 $ i $ へ移動することも可能です。 国 $ i $ の航空会社の飛行機は、$ 1 $ 度利用するたびに $ C_i $ 円の料金がかかります。 ケンさんは現在国 $ S $ にいて、国 $ T $ まで移動したいです。 飛行機を利用して移動するとき、飛行機の料金の合計の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ $ T $ $ X_1 $ $ Y_1 $ $ C_1 $ $ X_2 $ $ Y_2 $ $ C_2 $ $ \vdots $ $ X_N $ $ Y_N $ $ C_N $

国 $ S $ から国 $ T $ へ移動する際の、飛行機の料金の合計の最小値を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 0\ \leq\ X_i\ \leq\ 10^9 $ - $ 0\ \leq\ Y_i\ \leq\ 10^9 $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ - $ (X_i,Y_i)\ \neq\ (X_j,Y_j) $ ($ i\ \neq\ j $) - $ 1\ \leq\ S\ \leq\ N $ - $ 1\ \leq\ T\ \leq\ N $ - $ S\ \neq\ T $ - 飛行機のみを利用して国 $ S $ から国 $ T $ まで移動することができる。 - 入力される値はすべて整数である。 ### Sample Explanation 1 この例では、直通便は以下の $ 5 $ 種類が存在します。 - 国 $ 1 $ と国 $ 3 $ を結ぶ直通便。国 $ 1 $ の航空会社が運航しており、一度利用するのに $ 3 $ 円かかる。 - 国 $ 1 $ と国 $ 2 $ を結ぶ直通便。国 $ 2 $ の航空会社が運航しており、一度利用するのに $ 6 $ 円かかる。 - 国 $ 2 $ と国 $ 3 $ を結ぶ直通便。国 $ 2 $ の航空会社が運航しており、一度利用するのに $ 6 $ 円かかる。 - 国 $ 2 $ と国 $ 4 $ を結ぶ直通便。国 $ 2 $ の航空会社が運航しており、一度利用するのに $ 6 $ 円かかる。 - 国 $ 3 $ と国 $ 4 $ を結ぶ直通便。国 $ 4 $ の航空会社が運航しており、一度利用するのに $ 8 $ 円かかる。 国 $ 1 $ から国 $ 4 $ へ移動する場合は、国 $ 1→3→4 $ と移動すると料金の合計が $ 11 $ 円になり、これが最小です。