题目描述

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪。Farmer John 承担起向德克萨斯运送大量营养冰凉的牛奶的重任。

FJ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点在内，一共经过 $T$ 个城镇，编号为 $1$ 到 $T$。给定 $C$ 条双向道路，每条道路有一个通过费用。请你求从起始城镇 $T_s$ 到终点城镇 $T_e$ 的最小总费用。

输入格式

第一行输入四个整数 $T,C,T_s,T_e$。

接下来 $C$ 行，每行输入三个整数 $R_s,R_e,C_i$，表示 $R_s$ 和 $R_e$ 之间有一条双向道路，费用为 $C_i$。

输出格式

输出一个整数，表示从 $T_s$ 到 $T_e$ 的最小总费用。

样例

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

样例解释

一种最优路线为 $5\to6\to1\to4$，费用为 $3+1+3=7$。

数据范围

对于全部数据，满足 $1 \le T \le 2500$，$1 \le C \le 6200$，$1 \le R_s,R_e,T_s,T_e \le T$，$1 \le C_i \le 1000$。

数据保证至少存在一条从 $T_s$ 到 $T_e$ 的路径。