Taep Nitrous

/*
    Task    : Taep Nitrous
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 09 August 2022 [18:48]
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int v,w,k;
    bool operator < (const A&o) const{
        return w>o.w;
    }
};
priority_queue<A > heap;
vector<A > g[5010];
int dis[5010][110];
int main(){
    int n,m,k,u,v,w;
    scanf("%d %d %d",&n,&m,&k);
    while(m--){
        scanf("%d %d %d",&u,&v,&w);
        g[u].push_back({v,w,0});
        g[v].push_back({u,w,0});
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
            dis[i][j] = 1e9;

    dis[1][0] = 0;
    heap.push({1,0,0});
    while(!heap.empty()){
        A now = heap.top();
        heap.pop();
        for(auto x:g[now.v]){
            //no nitrous
            if(dis[now.v][now.k] + x.w < dis[x.v][now.k]){
                dis[x.v][now.k] = dis[now.v][now.k] + x.w;
                heap.push({x.v,dis[x.v][now.k],now.k});
            }
            //use nitrous
            if(dis[now.v][now.k] + x.w/2 < dis[x.v][now.k+1]){
                dis[x.v][now.k+1] = dis[now.v][now.k] + x.w/2;
                heap.push({x.v,dis[x.v][now.k+1],now.k+1});
            }
        }
    }
    int ans = 1e9;
    for(int i=0;i<=k;i++)
        ans = min(ans,dis[n][i]);
    printf("%d\n%d\n%d\n",dis[n][0],ans,dis[n][0] - ans);
    return 0;
}