#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cstdlib> #include<queue> #define ll long long using namespace std; const int maxn=10010; const int maxm=100010; const int maxk=25; int n,m,k,tot; int s,t; int head[maxn*maxk],nnext[maxm*2*maxk],to[maxm*2*maxk],length[maxm*2*maxk]; ll dis[maxn*maxk]; bool b[maxn*maxk]; void add(int x,int y,int l) { tot++; nnext[tot]=head[x]; head[x]=tot; to[tot]=y; length[tot]=l; } struct H { int id; ll d; }; bool operator < (const H &aa,const H &bb) { return aa.d>bb.d; } priority_queue<H> q; ll spfa() { for(int i=1;i<=(k+1)*n;i++) { dis[i]=1e15; }dis[1]=0; q.push((H){1,0}); b[1]=true; while(!q.empty()) { H tmp=q.top(); q.pop(); int now=tmp.id; b[now]=false; for(int i=head[now];i;i=nnext[i]) { int y=to[i]; if(dis[y]>dis[now]+length[i]) { dis[y]=dis[now]+length[i]; if(!b[y]) { b[y]=true; q.push((H){y,dis[y]}); } } } } return dis[(k+1)*n]; } int main() { //freopen("a.in","r",stdin); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); for(int l=1;l<=k;l++) { add(x+(l-1)*n,y+l*n,0); add(y+(l-1)*n,x+l*n,0); add(x+l*n,y+l*n,z); add(y+l*n,x+l*n,z); } } cout<<spfa(); fclose(stdin); fclose(stdout); return 0; }