AT_nikkei2019_final_f Flights

在二维平面上有 $N$ 个国家，编号为 $1$ 到 $N$。国家 $i$ 的坐标为 $(X_i, Y_i)$。 每个国家都有一家航空公司。对于国家 $i$，其航空公司会在满足 $X_j \leq X_i$ 且 $Y_j \leq Y_i$ 的所有 $j$（$j \neq i$）之间运营直达航班。这些直达航班是双向的。也就是说，可以利用国家 $i$ 的航空公司的飞机从国家 $i$ 前往国家 $j$，也可以从国家 $j$ 前往国家 $i$。每次使用国家 $i$ 的航空公司的飞机需要支付 $C_i$ 日元。 Ken 先生现在在国家 $S$，他想前往国家 $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$ 所需的最小飞机费用总和。

## 限制条件 - $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 在此例中，存在以下 $5$ 种直达航班： - 连接国家 $1$ 和国家 $3$ 的直达航班，由国家 $1$ 的航空公司运营，每次使用需支付 $3$ 日元。 - 连接国家 $1$ 和国家 $2$ 的直达航班，由国家 $2$ 的航空公司运营，每次使用需支付 $6$ 日元。 - 连接国家 $2$ 和国家 $3$ 的直达航班，由国家 $2$ 的航空公司运营，每次使用需支付 $6$ 日元。 - 连接国家 $2$ 和国家 $4$ 的直达航班，由国家 $2$ 的航空公司运营，每次使用需支付 $6$ 日元。 - 连接国家 $3$ 和国家 $4$ 的直达航班，由国家 $4$ 的航空公司运营，每次使用需支付 $8$ 日元。 从国家 $1$ 前往国家 $4$ 时，若选择 $1 \to 3 \to 4$，总费用为 $11$ 日元，这是最小值。 由 ChatGPT 4.1 翻译