問題文

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 まで移動したいです。 飛行機を利用して移動するとき、飛行機の料金の合計の最小値を求めてください。

制約

• 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 まで移動することができる。
• 入力される値はすべて整数である。

入力例 1

4 1 4
0 1 3
1 1 6
0 0 4
1 0 8

出力例 1

11

この例では、直通便は以下の 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 円になり、これが最小です。

入力例 2

9 3 6
2 3 9
1 4 2
0 4 16
1 3 77
3 3 12
4 0 96
4 2 41
2 1 17
3 4 45

出力例 2

104