#include<bits/stdc++.h>
using namespace std;
const long long MaxN = 2e5 + 5,MaxK=10, INF= 1e18;
long long n,m,k, d[MaxN][MaxK];
vector<pair<long long, long long>> vt[MaxN];
void dijikstra(long long v)
{
    priority_queue<tuple<long long, long long, long long>, vector<tuple<long long, long long, long long>>, greater<tuple<long long, long long, long long>>> pq;
    pq.push({0,1,0});
    while(!pq.empty())
    {
        long long du= get<0>(pq.top());
        long long u = get<1>(pq.top());
        long long state= get<2> (pq.top());
        pq.pop();
        if(du!=d[u][state]) continue;
        for (auto x : vt[u])
        {
            long long v = x.first;
            long long weight_v = x.second;
            if(d[v][state]>d[u][state]+weight_v)
            {
                d[v][state]=d[u][state]+weight_v;
                pq.push({d[v][state],v,state});
            }
            if(state<k&&d[v][state+1]>d[u][state])
            {
                d[v][state+1]=d[u][state];
                pq.push({d[v][state+1],v,state+1});
            }
        }
    }
}
void input()
{
    cin >> n >> m >> k;
    for (long long i=1; i<=m; i++)
    {
        long long u,v,w;
        cin >> u >> v >> w;
        vt[u].push_back ({v,w});
        vt[v].push_back({u,w});
    }
}
void output()
{
    for (long long i=1; i<=n; i++)
    {
        for (long long j=0; j<=k; j++)
        {
            d[i][j]=INF;
        }
    }
    d[1][0]=0;
    dijikstra(1);
    long long ans= INF;
    for(long long i=0; i<=k; i++)
    {
        ans=min(d[n][i],ans);
    }
    if(ans==INF)
    {
        cout << -1;
        return;
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    input();
    output();
}