---

竟然没有看出来是分层图==

---

#include<bits/stdc++.h>
using namespace std;
int ne,head[4200010],n,m,a,b,c,k,vist[4200010],d[4200010];
struct node{int to,nxt,dis;}eg[4200010];
void adde(int u,int v,int c){eg[++ne].nxt=head[u];eg[ne].dis=c;eg[ne].to=v;head[u]=ne;}
priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;
void dij(int s){
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
    int tt=q.top().second;
    q.pop();
    if(vist[tt])continue;
    vist[tt]=1;
    for(int i=head[tt];i;i=eg[i].nxt)
    if(d[eg[i].to]>d[tt]+eg[i].dis){d[eg[i].to]=d[tt]+eg[i].dis;
    q.push(make_pair(d[eg[i].to],eg[i].to));    }
    }
}
int main()
{
    memset(d,0x3f,sizeof(d));
    cin>>n>>m>>k;
    while(m--)
    {
        cin>>a>>b>>c;
        adde(a,b,c);adde(b,a,c);
        for(int i=1;i<=k;i++)
        {adde(a+i*n,b+i*n,c);adde(b+i*n,a+i*n,c);
        adde(a+(i-1)*n,b+i*n,0);adde(b+(i-1)*n,a+i*n,0);
        }
    }
    dij(1);
    cout<<d[(k+1)*n];
}