圆弧区间最短路问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


对于给定n个带权圆弧,计算从指定圆弧到所有圆弧的最短路。

Input

输入数据的第1行有2 个正整数n和m(n,m≤100000),表示有n个带权圆弧,并求第m个圆弧到所有圆弧的最短路。第2 行起每行有3 个整数,分别表示带权圆弧的左端点a,右端点b 和圆弧的权值w。其中,左端点a 和右端点b分别是按顺时针方向的圆心角,0 ≤  a < b ≤ 21600。

Output

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

Sample Input

4 1
0 10800 10
5400 1620 50
11100 18000 10
17400 600 30

Sample Output

160

Hint

 

Source