#2819. 热浪

热浪

题目描述

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

img

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

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

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

输入格式

1\red{1}行:4\red{4}个由空格隔开的整数T\red{T,}C\red{C,}Ts\red{T_s,}Te.\red{T_e.}

2\red{2}到第C+1\red{C+1}行:第i+1\red{i+1}行描述第i\red{i}条道路.有3\red{3}个由空格隔开的整数Rs\red{R_s,}Re\red{R_e,}Ci.\red{C_i.}

输出格式

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