#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
struct sd
{
    int p,j;
};
queue<sd>q;
vector<int>vv[20005],vv2[20005];
int n,m,u,v,k,mu[40005][23],em[40005][23],h,ans = 1e9;
signed main()
{
    cin >> n >> m >> k;
    q.push({1,0});
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d%d%d",&u,&v,&h);
        vv[u].push_back(v);vv2[u].push_back(h);
        vv[v].push_back(u);vv2[v].push_back(h);
    }
  //SPFA
    memset(em,0x3f,sizeof(em));
    em[1][0] = 0,mu[1][0] = 1;
    while(!q.empty())
    {
        sd w = q.front();
        q.pop();
        if(mu[w.p][w.j] == 0)continue;
        mu[w.p][w.j] = 0;
        for(int i = 0;i < vv[w.p].size();i ++)
        {
            if(w.j != k && em[vv[w.p][i]][w.j + 1] > em[w.p][w.j])
            {
                em[vv[w.p][i]][w.j + 1] = em[w.p][w.j],mu[vv[w.p][i]][w.j + 1] = 1;
                q.push({vv[w.p][i],w.j + 1});
            }
            if(em[vv[w.p][i]][w.j] > em[w.p][w.j] + vv2[w.p][i])
            {
                em[vv[w.p][i]][w.j] = em[w.p][w.j] + vv2[w.p][i],mu[vv[w.p][i]][w.j] = 1;
                q.push({vv[w.p][i],w.j});//点与已经使用几次
            }
        }
    }
    for(int i = 0;i <= k;i ++)
		ans = min(ans,em[n][i]);
	cout << ans << endl;
}