题目描述

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

约翰已经研究过可以把牛奶从威斯康星运送到得克萨斯州的路线.这些路线包括起始点和终 点先一共经过$\red{T(1≤}$$\red{T≤}$$\red{2500)}$个城镇，方便地标号为$\red{1}$到$\red{T.}$除了起点和终点外地每个城镇由两条 双向道路连向至少两个其它地城镇.每条道路有一个通过费用（包括油费，过路费等等） .考虑 这个有$\red{7}$个城镇的地图.城镇$\red{5}$是奶源，城镇$\red{4}$是终点（括号内的数字是道路的通过费用） .

经过路线$\red{5-6-3- 4}$总共需要花费$\red{3(5→}$$\red{6)+4(6→}$$\red{3)+3(3→}$$\red{4)= 10}$的费用.

给定一个地图，包含$\red{C(1≤}$$\red{C≤}$$\red{6200)}$条直接连接$\red{2}$个城镇的道路.每条道路由道路的起 点$\red{R_s，}$终点$\red{R_e(1 ≤}$$\red{R_s,R_e≤}$$\red{T)，}$和花费$\red{(1≤}$$\red{C_i≤}$$\red{1000)}$组成. 求从起始的城镇$\red{T_s(1≤}$$\red{T_s≤}$ $\red{T)}$到终点的城镇$\red{T_e(1≤}$$\red{T_e≤}$$\red{T)}$最小的总费用.

输入格式

第$\red{1}$行：$\red{4}$个由空格隔开的整数$\red{T，}$$\red{C，}$$\red{T_s，}$$\red{T_e.}$

第$\red{2}$到第$\red{C+1}$行：第$\red{i+1}$行描述第$\red{i}$条道路．有$\red{3}$个由空格隔开的整数$\red{R_s，}$$\red{R_e，}$$\red{C_i.}$

输出格式

一个单独的整数表示$\red{T_s}$到$\red{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