题目描述

有 $T$ 个城镇和 $C$ 条双向道路。通过一条道路需要支付给定的费用。请计算从城镇 $T_s$ 到城镇 $T_e$ 的最少总费用。

输入格式

第一行四个整数 $T,C,T_s,T_e$。接下来 $C$ 行，每行三个整数 $R_s,R_e,C_i$，表示一条双向道路的两个端点和费用。

输出格式

输出一个整数，表示最少总费用。

样例

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

数据范围

• $1\le T\le2500$，$1\le C\le6200$。
• $1\le T_s,T_e,R_s,R_e\le T$，$R_s\ne R_e$。
• $1\le C_i\le1000$。
• 除起点和终点外，每个城镇至少与两个不同的城镇相连。
• 允许同一对城镇之间有多条道路，保证起点能够到达终点。