热浪(heatwv) 【问题描述】 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来 不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John 此时以先天下

热浪(heatwv)8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【问题描述】8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John 此时以先天下之忧而忧，8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
以减轻德克萨斯人忍受酷暑的痛苦。8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
FJ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
和终点先一共经过 T (1 <= T <= 2,500)个城镇，方便地标号為 1 到 T。除了起点和终点外的8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
每个城镇由两条双向道路连向至少两个其它的城镇。每条道路有一个通过费用（包括油费，8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
过路费等等）。8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
给定一个地图，包含 C (1 <= C <= 6,200)条直接连接 2 个城镇的道路。每条道路由道路8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
的起点 Rs，终点 Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
的城镇 Ts (1 <= Ts <= T)到终点的城镇 Te(1 <= Te <= T)最小的总费用。8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入文件】8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行: 4 个由空格隔开的整数: T, C, Ts, Te8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路。有 3 个由空格隔开的整数: Rs, Re 和 Ci8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出文件】8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一个单独的整数表示从 Ts 到 Te 的最小总费用。数据保证至少存在一条道路。8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输入】8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
7 11 5 48sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 4 28sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 4 38sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
7 2 28sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 4 38sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5 7 58sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
7 3 38sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
6 1 18sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
6 3 48sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 4 38sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5 6 38sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
7 2 18sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输出】8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
78sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例说明】8sf100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5->6->1->4 (3 + 1 + 3)