区间图最短路问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


对于给定n个带权区间,计算从最左区间到所有区间的最短路。最左区间是指n个区间中右端点最小的那个区间。

Input

输入数据的第1 行是正整数n,表示有n 个带权区间。第2行起每行有3 个正整数,分别表示带权区间的左端点,右端点和区间的权值。n≤1000000。

Output

程序结束时,将计算出的最左区间到所有区间的最短路之和输出。当最左区间与区间i 不连通时,最左区间与区间i 之间的最短路不计入。

Sample Input

10
1 4 15
5 6 12
3 7 13
2 9 17
10 13 17
12 14 19
11 15 21
16 18 13
17 19 15
8 20 18

Sample Output

500

Hint

 

Source