题目描述

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生产富含奶油的乳制品。Farmer John 此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

FJ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点在内一共经过 $T$ 个城镇，方便地标号为 $1$ 到 $T$。除了起点和终点外的每个城镇由两条双向道路连向至少两个其它的城镇。每条道路有一个通过费用（包括油费，过路费等）。

给定一个地图，包含 $C$ 条直接连接 $2$ 个城镇的双向道路。每条道路由起点 $R_s$，终点 $R_e$ 和花费 $C_i$ 组成。求从起始的城镇 $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 \to 6 \to 1 \to 4$，总费用为 $3 + 1 + 3 = 7$。

数据范围

• $1 \le T \le 2\,500$
• $1 \le C \le 6\,200$
• $1 \le T_s, T_e, R_s, R_e \le T$
• $1 \le C_i \le 1\,000$