2497: 热浪

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生产富含奶油的乳制品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。
FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 ≤ T ≤ 2,500)个城镇,方便地标号为1到T。每个城镇至少有一条双向道路连其它的城镇(两个城镇可能有多条道路)。每条道路有一个通过费用(包括油费,过路费等等)。
给定一个地图,包含C (1 ≤ C ≤ 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs,终点Re (1 ≤ Rs ≤ T; 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和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

提示