F - Flights

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900

問題文

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

入力

入力は以下の形式で標準入力から与えられる。

N S T
X_1 Y_1 C_1
X_2 Y_2 C_2
\vdots
X_N Y_N C_N

出力

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