题目描述

一个地区有 $n$ 个城镇和 $m$ 条双向道路，每条道路有一个通行代价。请计算从城镇 $s$ 到城镇 $t$ 的最短路径代价。

输入格式

第一行四个正整数 $n, m, s, t$。
接下来 $m$ 行，每行三个正整数 $u, v, w$，表示一条连接城镇 $u$ 和 $v$、代价为 $w$ 的双向道路。

输出格式

输出一行一个整数，表示从 $s$ 到 $t$ 的最短路径代价。

样例

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

7

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 2500$，$1\le m \le 6200$，$1\le w \le 1000$。

【样例说明】
$5 \to 6 \to 1 \to 4$ 为最短路径，代价为 $3+1+3 = 7$。