解题思路

边权为正，求最短路，但全程至多把一条已有通道的费用改成 $0$。直接把某条边改成 $0$ 再跑 Dijkstra，要对每条边做一次，最大数据过不了。

关键观察：最优路线要么不用协议，要么恰好免费走一条通道 $(u,v)$。后一种情况，路线被拆成三段：$s$ 走到 $u$（全部按原价）、免费穿过这条通道、$v$ 走到 $t$（全部按原价）。两头都是普通最短路。

1. 在原图上从 $s$ 做一次堆优化 Dijkstra，得到 $ds[u]$。
2. 再从 $t$ 做一次，得到 $dt[u]$。无向图不用建反图。
3. 不用协议时，答案是 $ds[t]$。

题目内容

勘探队要从入口走到出口。洞穴有 $n$ 个洞室，编号 $1\sim n$，以及 $m$ 条双向通道。每条通道连接两个洞室。沿一条长度为 $w$ 的通道走，路程增加 $w$。同一条通道、同一个洞室都可以多次经过。

队伍带了一次应急协议：全程至多可以把一条通道的通行路程记为 $0$（走这条通道时不再累加它的长度）。也可以不用这次协议。协议不能凭空造出新通道，只能用在已经存在的通道上，且整段行程里最多用一次。

入口在洞室 $s$，出口在洞室 $t$。请给出最短总路程。无法到达时输出 $-1$。

输入描述

第一行四个整数 $n$、$m$、$s$、$t$。

接下来 $m$ 行，每行三个整数 $u$、$v$、$w$，表示洞室 $u$ 与 $v$ 之间有一条长度为 $w$ 的双向通道。

约束

$1 \le n \le 8000$

$0 \le m \le 2\times 10^4$

$1 \le s,t,u,v \le n$

$1 \le w \le 10^6$

允许重边和自环

输出描述

输出一个整数：最短总路程；无法到达则输出 $-1$。

样例1

输入

4 4 1 4
1 2 5
2 4 5
1 3 100
3 4 1

输出

1

说明

不用协议时，走 $1\to 2\to 4$，路程 $10$。若把 $1\to 3$ 这条看起来很长的通道免费走掉，再走 $3\to 4$，路程 $1$。只在原来的最短路上挑一条免费，得不到这个答案。

样例2

输入

3 1 1 3
1 2 5

输出

-1

说明

洞室 $3$ 与入口不连通，应急协议也不能造出新通道。