问题描述

JAG王国由$N$个城市和$M$条双向道路组成。第$i$条道路$(u_i,v_i,c_i)$连接城市$u_i$和城市$v_i$，长度为$c_i$。某一天，作为JAG王国的居民，你决定从城市$S$前往城市$T$。然而，你了解到JAG王国中有一条道路正在施工中，你无法通过这条道路。你不知道是哪条道路在施工。只有当你身处与道路相连的城市时，你才能得知哪条道路正在施工。

你的任务是在最坏情况下最小化路径的总长度。你不需要事先决定要走的路线，可以随时选择下一步去哪里。如果在最坏情况下无法到达城市$T$，输出-1。

输入

输入包含一个单独的测试用例，格式如下所示。

$N$ $M$ $S$ $T$ $u_1$ $v_1$ $c_1$ $\\vdots$ $u_M$ $v_M$ $c_M$

第一行包含四个整数$N$，$M$，$S$和$T$，其中$N$是城市的数量($2 \\leq N \\leq 100{,}000$)，$M$是双向道路的数量($1 \\leq M \\leq 200{,}000$)，$S$是你的出发城市($1 \\le S \\le N$)，$T$是你想要到达的城市($1 \\le T \\le N$, $S \\neq T$)。接下来的$M$行表示道路信息：$M$行中的第$i$行由三个整数$u_i$，$v_i$，$c_i$组成，表示第$i$条道路连接城市$u_i$和城市$v_i$($1 \\leq u_i, v_i, \\leq N$，$u_i \\neq v_i$)，长度为$c_i$($1 \\leq c_i \\leq 10^9$)。如果没有道路在施工，可以假设所有城市对之间都有连接。也就是说，对于所有城市$x$和$y$，存在至少一条通过给定道路的路径从城市$x$到城市$y$。还保证没有重复的边，即$\\{u_i, v_i\\} \\neq \\{u_j, v_j\\}$对于所有$1 \\le i < j \\le M$。

输出

输出在最坏情况下的最小总路线长度。如果在最坏情况下无法到达城市$T$，输出-1。

示例输入1

3 3 1 3
1 2 1
2 3 5
1 3 3

示例输出1

6

示例输入2

4 4 1 4
1 2 1
2 4 1
1 3 1
3 4 1

示例输出2

4

示例输入3

5 4 4 1
1 2 3
2 3 4
3 4 5
4 5 6

示例输出3

-1