AT_joi2018ho_d 定期券 (Commuter Pass)

JOI 君居住的城市中有 $N$ 个车站，编号为 $1$ 到 $N$。同时，还有 $M$ 条铁路线，编号为 $1$ 到 $M$。每条铁路线 $i$ ($1 \leq i \leq M$) 连接车站 $A_i$ 和车站 $B_i$，票价为 $C_i$ 日元。 JOI 君住在车站 $S$ 附近，学校在车站 $T$ 附近，因此他计划购买一张从车站 $S$ 到车站 $T$ 的定期票。购买该定期票时，需要选择一条从 $S$ 到 $T$ 的最低票价路径。购票之后，他可以在这条指定路径上的所有铁路线自由通行。 此外，JOI 君还频繁访问车站 $U$ 和车站 $V$ 附近的书店。他希望选择的定期票能帮助他降低从车站 $U$ 到车站 $V$ 的出行费用。 从车站 $U$ 到车站 $V$ 时，若经过的铁路线 $i$ 包含在定期票所指定的路径中，则票价为 $0$ 日元；否则，票价为 $C_i$ 日元。我们的目标是找到一种选择定期票路径的方法，使得从车站 $U$ 到车站 $V$ 的总票价最小。

从标准输入中读取： - 第一行输入两个整数 $N$ 和 $M$，分别表示车站数量和铁路线数量。 - 第二行输入两个整数 $S$ 和 $T$，表示欲购买定期票的起点和终点车站。 - 第三行输入两个整数 $U$ 和 $V$，表示希望计算票价最小化的起点和终点车站。 - 接下来的 $M$ 行，每行包含三个整数 $A_i, B_i, C_i$，表示第 $i$ 条铁路线连接车站 $A_i$ 和车站 $B_i$，票价为 $C_i$ 日元。

输出一个整数，表示通过合理选择定期票路径后，从车站 $U$ 到车站 $V$ 的最小票价。

### 限制 所有数据满足： - $2 \leq N \leq 100,000$ - $1 \leq M \leq 200,000$ - $1 \leq S, T, U, V \leq N$ - $S \neq T$ - $U \neq V$ - $S \neq U$ 或 $T \neq V$ - 任意两个车站间至少有一条可行的铁路线 - 对于 $1 \leq i \neq j \leq M$，$A_i \neq A_j$ 或 $B_i \neq B_j$ - $1 \leq C_i \leq 1,000,000,000$ ### 子任务 #### 子任务 1 [16 分] - 满足 $S = U$。 #### 子任务 2 [15 分] - 从车站 $S$ 到车站 $T$ 的最优路径唯一。 #### 子任务 3 [24 分] - $N \leq 300$。 #### 子任务 4 [45 分] - 无额外限制。 ### 示例解释 在示例中，从车站 $1$ 到车站 $4$ 的最小票价路径是 $1 \to 2 \to 3 \to 5 \to 4$。在该路径上，除了 $5$ 号铁路线需支付 $2$ 日元外，其他路线均免费，总费用为 $2$ 日元。 **本翻译由 AI 自动生成**