旅行
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小蓝想要从  号城市去往  号城市 , 城市之间有  条双向线路,对于第  条线路,连接  ,  并且需要一个  的车费 ,小蓝会在白天逗留,夜晚出发去下一座城, 所以他每天只会乘坐一次汽车,移动一个城市,并且在第二天早上的同一时间到达另一个城市。现在进入城市需要  小时内核酸检测报告, 小蓝在  号城市不需要做核酸,他只会在进站时补做核酸,所以进入第  个城市时他需要补做核酸  。所有城市的核酸检测费用均为  ,小蓝想让你计算一下到达  号城市的最小花费是多少。

输入描述:

第一行三个整数 n , m , x  。
接下来m行每行三个整数 u , v , w  ，表示城市 u 与城市 v 之间有一条车票费用为 w 的汽车线路。

输出描述:

输出一行一个整数,表示最小花费。
示例1

输入

复制 
6 5 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

输出

复制 
8

说明

路径为 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6,  进入   号城市时没有核酸检测记录需要补做核酸检测花费  ,从   号城市到  号城市时有 48 内小时的核酸检测记录(离上一次检测间隔 24 小时)所以花费   , 从  号城市到  号城市没有核酸检测记录(离上一次检测间隔 48 小时),需要补做核酸检测花费  ,从  号城市到  号城市有核酸检测记录,所以花费  ,从5号城市到6号城市时需没有核酸检测记录需要要补做一次核酸检测,花费 1 + 1 。最终花费 8 。

备注:

保证存在从 1 号城市到 n 城市的线路。