配点: 100 点
JOI 在你居住的城市 有 N 个站,每个站都有 它的编号为 1, 2, \ldots, N 。另外,M 有两条铁路线,各有 它的编号为 1, 2, \ldots, M 。铁路线 i (1 \leqq i \leqq M) 是车站 A_i 和车站 B_i 双向转乘,票价为 C_i 这是日元。
JOI 君羽站 我住在 S 和车站附近 我在 T 附近的 IOI 高中就读。因此,我决定购买一张连接两者的月票。购买月票时,请前往车站 您必须指定一条在 S 和车站 T 之间行驶且票价最低的路线。使用这张月票,您可以在指定路线所包含的铁路线路上双向自由上下车。
JOI 你是站 U 和车站 我也经常去 V 附近的书店。那么,车站 U 从车站 我想购买一张通勤卡,这样前往 V 的票价就会尽可能低。 前往
駅 U 从车站 我想购买一张通勤卡,这样前往 V 时,首先前往车站。 前往 U 从车站 我想购买一张通勤卡,这样前往 V 的路线 1 选择一项。该路线包含的铁路线 在 i 支付的票价是 如果购买月票时指定的路线中包含
- 鉄道路線 i , 如果购买月票时指定的路线不包含0 円
- 鉄道路線 i ,C_i 円
变为。这笔费用总计为 这是前往 U 从车站 我想购买一张通勤卡,这样前往 V 的票价。购买月票时选择指定路线时的车站 我想了解前往 U 从车站 我想购买一张通勤卡,这样前往 V 所需的最低票价。
課題
购买月票时选择指定路线时的车站 编写一个程序来查找前往 U 从车站 我想购买一张通勤卡,这样前往 V 的最低票价。
入力
从标准输入读取以下输入。 写入
- 1 行中,2 整数 N, M 。这些都在JOI居住的城市。 N 站和 M 表示有两条铁路线。 写入
- 2 行中,2 整数 S, T 。这些是 JOI Kimiga 站 表示购买前往 S 从车站 我想购买一张通勤卡,这样前往 T 的通勤卡。 表示我们希望尽量减少前往
- 3 行中,2 整数 U, V 。这些是 JOI Kimiga 站 表示购买前往 U 从车站 我想购买一张通勤卡,这样前往 V 所需的票价。
- 继续 M 行中的 i 行目 (1 \leqq i \leqq M)有 写入3 整数 A_i, B_i, C_i 。这些是铁路线 i 是车站 A_i 和车站 B_i 双向转乘,票价为 C_i 代表一个圆圈。
出力
标准输出包含购买通勤卡时的车站信息。 当成功指定到 S 从车站 我想购买一张通勤卡,这样前往 T 的路线时,该站 前往 U 从车站 我想购买一张通勤卡,这样前往 V 的最低票价 1 行。 在
制限
所有输入数据满足以下条件。
- 2 \leqq N \leqq 100\,000.
- 1 \leqq M \leqq 200\,000.
- 1 \leqq S \leqq N.
- 1 \leqq T \leqq N.
- 1 \leqq U \leqq N.
- 1 \leqq V \leqq N.
- S \neq T.
- U \neq V.
- S \neq U 或 T \neq V.
- 从任何车站到任何其他车站 1 可使用多条铁路线到达。 对于
- 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M).
- 1 \leqq i < j \leqq M ,A_i \neq A_j 或 B_i \neq B_j.
- 1 \leqq Ci \leqq 1\,000\,000\,000 (1 \leqq i \leqq M).
小課題
小課題 1 [16 点]
- S = U 很满意。 可用于以最低票价前往
小課題 2 [15 点]
- 駅 S 从车站 我想购买一张通勤卡,这样前往 T 的路线是 1 只有一条街。
小課題 3 [24 点]
- N \leqq 300 很满意。 可用于以最低票价前往
小課題 4 [45 点]
- 没有其他限制。
入力例 1
6 6 1 6 1 4 1 2 1 2 3 1 3 5 1 2 4 3 4 5 2 5 6 1
出力例 1
2
在本输入示例中,购买月票时可以指定的路线是车站 仅限路线 1 → 駅 2 → 駅 3 → 駅 5 → 駅 6 。 为了最大限度地减少前往
駅 1 从车站 我想购买一张通勤卡,这样前往 4 的费用,车站 您可以选择路线 1 → 駅 2 → 駅 3 → 駅 5 → 駅 4 。如果您选择这条路线,每条铁路线需支付的票价为: 连接
- 駅 4 和车站 5 的铁路线 在 5 中,2 円.
- 在其他铁路线上,0 円.
,所以总票价是 2 变成日元。
入力例 2
6 5 1 2 3 6 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000
出力例 2
3000000000
在此输入示例中,站 请勿使用通勤卡前往 3 从车站 我想购买一张通勤卡,这样前往 6 。 给出了
入力例 3
8 8 5 7 6 8 1 2 2 2 3 3 3 4 4 1 4 1 1 5 5 2 6 6 3 7 7 4 8 8
出力例 3
15
入力例 4
5 5 1 5 2 3 1 2 1 2 3 10 2 4 10 3 5 10 4 5 10
出力例 4
0
入力例 5
10 15 6 8 7 9 2 7 12 8 10 17 1 3 1 3 8 14 5 7 15 2 3 7 1 10 14 3 6 12 1 5 10 8 9 1 2 9 7 1 4 1 1 8 1 2 4 7 5 6 16
出力例 5
19