U121369 小李白坐地铁

济南地铁已经开通了R1和R3线。 小李白也兴奋地在高考前去体验了一下，发现可以用公交卡刷卡并且车站文化氛围很浓厚$qwq$

小李白来到了一个大城市，他住在了一个五星级酒店，他规划着接下来的几天内在大城市的城区内坐地铁游玩景点。这个城市有着完善的地铁网络。但是非常不幸的是，地铁全是单向行驶的。 小李白每天都要坐地铁去一个景点游玩，然后傍晚时分坐地铁回来。第一天去编号为2的景点，第二天去编号为3的景点......小李白要去过所有的景点才会罢休$qwq$。我们设每一个地铁站点都是一个景点。对于每一天的景点，小李白都想知道如何坐地铁才能使得来回总时间合最小。他会给你整个城市的地铁路线和站点图，并且向你求助这个问题。 有$n$个站点,$m$个站点间的地铁线路。小李白所住的酒店需要耗时时间$d$才能到地铁站$1$，也就是从站点$1$开始坐地铁。 数据会给你每对站点之间的路线长度$w$.

第1行：$n,m,d$ 第$2到m+1$行,u,v,w,表示从站点u到站点v有一条长度为w的地铁路线。

小李白每天在路上耗时的和$sum$。 为了更方便的解释，我们设每天在路上花费的时间为$time[i]$，小李白要去的景点数为$k$。 那么答案就是$\sum_{i=1}^k time[i] $。

对于$ 30\%$的数据,$n=1$ 对于$100\%$的数据： $n\leqslant1000$ $m\leqslant100000$ $w\leqslant200$ $d\leqslant1500000$ 均为整数。 ~~小李白远远不如他的朋友**ych**强，所以只能结合高考前放假经历随便出了个题~~ 注意空间时间限制$qwq$。 ## $qwq_{ych_{Orz}}^{ybr_{csl}^{tcl}}$