BOJ 1162

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 10001
#define INF 1e11

typedef long long ll;

struct node{
    int cur;
    ll cur_w;
    int cnt;
    bool operator < (const node& a)const{
        return a.cur_w < cur_w;
    }
};
ll dist[MAXN][21];
priority_queue<node> pq;
vector<pair<int,ll> > adj[MAXN];
int N,M,K;
void dijkstra(){
    pq.push({1,0,0});
    dist[1][0] = 0;
    while (!pq.empty()){
        int cur = pq.top().cur;
        ll cur_w = pq.top().cur_w;
        int cur_cnt = pq.top().cnt;
        pq.pop();
        if (!(dist[cur][cur_cnt-1]==cur_w|| dist[cur][cur_cnt]==cur_w)) continue;
        for (int i = 0 ; i < adj[cur].size(); i++){
            int next = adj[cur][i].first;
            int next_w = adj[cur][i].second;
            if (cur_cnt <K){
                if (dist[next][cur_cnt+1] > dist[cur][cur_cnt]){
                    dist[next][cur_cnt+1] = dist[cur][cur_cnt];
                    pq.push({next,dist[next][cur_cnt+1],cur_cnt+1});
                }
            }
            if (dist[next][cur_cnt]>next_w + cur_w){
                dist[next][cur_cnt] = next_w + cur_w;
                pq.push({next,dist[next][cur_cnt],cur_cnt});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i = 1 ; i <=N;i++){
        for (int j = 0 ;j <= K; j++){
            dist[i][j] = INF;
        }
    }
    while (M--){
        int u,v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dijkstra();
    ll ans = INF;
    for (int i = 0; i <= K; i++){
        ans = min(ans,dist[N][i]);
    }
    cout << ans <<"\n";
    return 0;
}