图上最短路II

题目描述

给定一张 $n$ 点 $m$ 条边构成的带权无向图，并且给定起点 $S$ 以及终点 $T$，请求出 $S$ 到 $T$ 的最短路径的长度，如果 $S$ 和 $T$ 之间不连通，则输出-1。

输入格式

第一行为四个整数 $n,m,S,T$，分别表示点数，边数，起点和终点。 接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示节点 $u$ 和节点 $v$ 之间存在一条长度为 $w$ 的边。

数据范围: $1 \le n, m \le 2 \times 10^5$ $1 \le S, T, u, v \le n$ $1 \le w \le 10^9$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

5

提示

一条可能的最短路，长度为5。