#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m,k;
int s,t;
int dist[10005][25];//从源点出发到达i点，且升级了j次之后的消耗的时间
bool vis[10005][25];

struct Edge
{
    int from,to,w;
};

vector<Edge>edges;
vector<int>G[maxn];

void init()
{
    for(int i=0;i<n;i++)
        G[i].clear();
    edges.clear();
}

void add(int from,int to,int w)
{
    edges.push_back({from,to,w});
    int m=edges.size();
    G[from].push_back(m-1);
}

struct HeapNode
{
    int u,cnt,d;
    bool operator <(const HeapNode&rhs)const{
            return d>rhs.d;
    }
};

priority_queue<HeapNode>q;
void dijkstra()
{

    memset(vis,false,sizeof(vis));
    memset(dist,inf,sizeof(dist));
    q.push({1,0,0});
    dist[1][0]=0;
    while(!q.empty())
    {
        HeapNode temp=q.top();
        q.pop();
        int u=temp.u,cnt=temp.cnt,d=temp.d;
        if(cnt==k)
            continue;
        if(vis[u][cnt])
            continue;
        vis[u][cnt]=true;
        for(int i=0;i<G[u].size();i++)
        {
            Edge e=edges[G[u][i]];
           if(dist[e.to][cnt]>dist[u][cnt]+e.w)
           {
               dist[e.to][cnt]=dist[u][cnt]+e.w;
                q.push({e.to,cnt,dist[e.to][cnt]});


           }
            if(dist[e.to][cnt+1]>dist[u][cnt])
           {
               dist[e.to][cnt+1]=dist[u][cnt];
               q.push({e.to,cnt+1,dist[e.to][cnt+1]});
           }
        }
    }
}



int main()
{
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
   for(int i=0;i<m;i++)
   {
       int u,v,w;
       cin>>u>>v>>w;
       add(u,v,w);
       add(v,u,w);
   }
   dijkstra();
   cout<<dist[n][k];

}

就过了三个点，为什么emmmmm