Problem Description

In a 2-dimensional plane, there are $ N $ countries numbered from $ 1 $ to $ N $. Country $ i $ is located at coordinates $ (X_i, Y_i) $.

Each country has an airline. The airline of country $ i $ operates direct flights to all countries $ j $ ($j \neq i$) that satisfy $X_j \leq X_i$ and $Y_j \leq Y_i$. These direct flights are bidirectional, meaning that you can travel from country $ i $ to country $ j $ and from country $ j $ to country $ i $ using the airline of country $ i $. Each use of the airplane of country $ i $ costs $ C_i $ yen.

Ken is currently in country $ S $ and wants to travel to country $ T $. Find the minimum total cost of airplane fares to travel from country $ S $ to country $ T $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the minimum total cost of airplane fares to travel from country $ S $ to country $ T $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

11

Sample Input #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

Sample Output #2

104

Notes/Hints

Constraints

• $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$
• It is possible to travel from country $ S $ to country $ T $ using only airplanes.
• All input values are integers.

Sample Explanation 1

In this example, there are the following 5 types of direct flights:
- Direct flight between country $ 1 $ and country $ 3 $, operated by the airline of country $ 1 $, costing $ 3 $ yen per use.
- Direct flight between country $ 1 $ and country $ 2 $, operated by the airline of country $ 2 $, costing $ 6 $ yen per use.
- Direct flight between country $ 2 $ and country $ 3 $, operated by the airline of country $ 2 $, costing $ 6 $ yen per use.
- Direct flight between country $ 2 $ and country $ 4 $, operated by the airline of country $ 2 $, costing $ 6 $ yen per use.
- Direct flight between country $ 3 $ and country $ 4 $, operated by the airline of country $ 4 $, costing $ 8 $ yen per use.
To travel from country $ 1 $ to country $ 4 $, moving via $1 \rightarrow 3 \rightarrow 4$ results in a total cost of $ 11 $ yen, which is the minimum.

见题面 Input 部分

见题面 Output 部分