问题 26180. -- 热浪

26180: 热浪

时间限制: 1 Sec  内存限制: 128 MB
献花: 3  解决: 1
[献花][花圈]

题目描述

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

Farmer John已经研究过可以把牛奶从威斯康辛运送到德克萨斯州的路线。这些路线包括起点和终点在内一共经过T(1 <= T <= 2500)个城镇,标号为1到T。除了起点和终点外的每个城镇由两条双向道路连向其他城镇。每条道路有一个通过费用(包括油费,过路费等)。

给定一个地图,包含C(1 <= C <= 6200)条直接连接2个城镇的道路。每条道路由道路的起点Rs、终点Re(1 <= Rs <=T; 1 <= Re <= T)和花费Ci(1 <= Ci <= 1000)组成。求从起始的城镇Ts(1 <= Ts <= T)到终点城镇Te(1 <= Te <= T)最小的总费用。

输入

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

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

输出

一个单独的整数,表示从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 = 7



上传者:吕红波

来源

[献花][花圈]