```cpp
#include <bits/stdc++.h>
using namespace std;
int tmp,n,m,i,x,y,z,ti,tmpp;
int dis[300000+5],h[300000+5];
bool b[300000+5],bo[300000+5];
struct EDGE{
int from,to,next,w;
};
EDGE e[10100000];
struct cmp{
bool operator()(int a,int b){
return dis[a]>dis[b];
}
};
priority_queue<int,vector<int>,cmp> q;
void add(int a,int b,int c){
tmp++;
e[tmp].from=a+n*ti;
e[tmp].to=b+n*ti;
e[tmp].w=c;
e[tmp].next=h[a+n*ti];
h[a+n*ti]=tmp;
for(int j=1;j<=ti;j++){
tmp++;
e[tmp].from=a+n*(j-1);
e[tmp].to=b+n*j;
e[tmp].w=0;
e[tmp].next=h[a+n*(j-1)];
h[a+n*(j-1)]=tmp;
tmp++;
e[tmp].from=a+n*(j-1);
e[tmp].to=b+n*(j-1);
e[tmp].w=c;
e[tmp].next=h[a+n*(j-1)];
h[a+n*(j-1)]=tmp;
}
}
void dij(int k){
dis[k]=0;
q.push(k);
while(q.empty()==false){
int t=q.top();
q.pop();
b[k]=true;
int s=h[t];
while(s!=0){
if(dis[e[s].to]>dis[t]+e[s].w){
dis[e[s].to]=dis[t]+e[s].w;
if(b[e[s].to]==false&&bo[e[s].to]==false){
q.push(e[s].to);
bo[e[s].to]=true;
}
}
s=e[s].next;
}
}
}
int main(){
cin>>n>>m>>ti;
for(i=1;i<=m;i++){
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
for(i=1;i<=n*(ti+1);i++){
dis[i]=1000000000;
}
dij(1);
int ans=dis[n];
for(i=1;i<=ti;i++)
ans=min(ans,dis[n+n*i]);
cout<<ans;
return 0;
}
```
by Tofu @ 2019-04-11 19:16:22