题目描述
小蓝想要从 111 号城市去往 nnn 号城市 , 城市之间有 mmm 条双向线路,对于第 iii 条线路,连接 uiu_iui , viv_ivi 并且需要一个 wiw_iwi 的车费 ,小蓝会在白天逗留,夜晚出发去下一座城, 所以他每天只会乘坐一次汽车,移动一个城市,并且在第二天早上的同一时间到达另一个城市。现在进入城市需要 484848 小时内核酸检测报告, 小蓝在 111 号城市不需要做核酸,他只会在进站时补做核酸,所以进入第 222 个城市时他需要补做核酸 。所有城市的核酸检测费用均为 xxx ,小蓝想让你计算一下到达 nnn 号城市的最小花费是多少。
输入
第一行三个整数 nnn , mmm , xxx (1≤n,x≤105),(n−1≤m≤2×105)(1 \le n , x \le 10^5),(n-1 \le m \le 2 \times 10^5 )(1≤n,x≤105),(n−1≤m≤2×105) 。
接下来m行每行三个整数 uuu , vvv , www (1≤u,v≤n,1≤w≤105)(1\le u,v \le n, 1\le w \le 10^5)(1≤u,v≤n,1≤w≤105)，表示城市 uuu 与城市 vvv 之间有一条车票费用为 www 的汽车线路。
输出
输出一行一个整数,表示最小花费。
样例输入 Copy
6 5 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
样例输出 Copy
8
提示
路径为 1→2→3→4→5→61 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 61→2→3→4→5→6, 进入 222 号城市时没有核酸检测记录需要补做核酸检测花费 1+11+11+1 ,从 222 号城市到 333 号城市时有 484848 内小时的核酸检测记录(离上一次检测间隔 242424 小时)所以花费 111 , 从 333 号城市到 444 号城市没有核酸检测记录(离上一次检测间隔 484848 小时),需要补做核酸检测花费 1+11+11+1 ,从 444 号城市到 555 号城市有核酸检测记录,所以花费 111 ,从555号城市到666号城市时需没有核酸检测记录需要要补做一次核酸检测,花费 1+11 + 11+1 。最终花费 888 。