#3408. [Usaco2009 Oct]Heat Wave 热浪

题目描述

.jpg)

输入格式

第1行：4个由空格隔开的整数T，C，Ts，Te.

第2到第C+1行：第i+l行描述第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

数据范围与提示