题目描述

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

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

给定一个地图，包含$C (1 ≤ C ≤ 6,200)$条直接连接$2$个城镇的道路。每条道路由道路的起点$Rs$，终点$Re (1 ≤ Rs ≤ T;\space 1 ≤ Re ≤ T)$，和花费$(1 ≤ Ci ≤ 1,000)$组成。求从起始的城镇$Ts (1 ≤ Ts ≤ T)$到终点的城镇$Te(1 ≤ Te ≤ T)$最小的总费用。

输入

第一行: $4$个由空格隔开的整数:$T, C, Ts, Te$;

第$2$到第$C+1$行: 第$i+1$行描述第$i$条道路。有$3$个由空格隔开的整数: $Rs, Re$和$C_i$。

输出

一个单独的整数表示从$Ts$到$Te$的最小总费用。数据保证至少存在一条道路。

样例

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->6->1->4 (3 + 1 + 3)$

来源

一本通在线评测