城市传送费

题目描述

有 n 座城市和 m 条双向传送通道，每条通道有费用。求从城市 s 到城市 t 的最小费用。

输入格式

第一行四个整数 n,m,s,t。接下来 m 行，每行三个整数 u,v,w，表示一条费用为 w 的双向通道。

输出格式

输出一个整数，表示最小费用；若无法到达，输出 -1。

数据范围

1 ≤ n ≤ 10^5，0 ≤ m ≤ 2 imes10^5，1 ≤ w ≤ 10^9。

样例输入

3 3 1 3
1 2 5
2 3 6
1 3 20

样例输出

11

第一行四个整数 n,m,s,t。接下来 m 行，每行三个整数 u,v,w，表示一条费用为 w 的双向通道。

输出一个整数，表示最小费用；若无法到达，输出 -1。

1 ≤ n ≤ 10^5，0 ≤ m ≤ 2 imes10^5，1 ≤ w ≤ 10^9。