#include <bits/stdc++.h>
#define llong long long
#define dlong long double
#define ulong unsigned llong
#define ilong __int128
#define int llong

using namespace std;

const ulong N=1e5+10;
const ulong K=20;
int n,m,k,s,t,ans=INT_MAX;
struct gh
{
    int v,w;
};
vector<vector<gh>> v(N*K);
int d[N*K];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
bool fi[N*K];

inline void read()
{
    freopen("P2939_2.in","r",stdin);
    //freopen("","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return;
}
inline void ETL()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    pq.push({0,1});
    while(pq.size())
    {
        int id=pq.top().second;
        int w=pq.top().first;
        pq.pop();
        if(fi[id])
            continue;
        fi[id]=true;
        for(auto y:v[id])
        {
            if(d[id]+y.w<d[y.v])
            {
                d[y.v]=d[id]+y.w;
                pq.push({d[y.v],y.v});
            }
        }
    }
    return;
}

signed main(/*int argc, const char * argv[]*/)
{
    read();
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
        for(int j=1;j<=k;j++)
        {
            v[x+(j-1)*n].push_back({y+j*n,0});
            v[y+(j-1)*n].push_back({x+j*n,0});
            v[x+j*n].push_back({y+j*n,z});
            v[y+j*n].push_back({x+j*n,z});
        }
    }
    ETL();
    for(int i=0;i<=n;i++)
    	ans=min(ans,d[t+i*n]);
    cout<<ans<<"\n";
    return 0;
}