#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define maxk 55#define maxv 5050#define maxe 5000050#define inf 2147483647using namespace std;int n,m,k,x,y,z,v[maxk][maxk],tot=0,dis[maxv],g[maxv],nume=0,ans=inf;bool vis[maxv];struct edge{    int v,w,nxt;}e[maxe];queue <int> q;void addedge(int u,int v,int w){    e[++nume].v=v;    e[nume].w=w;    e[nume].nxt=g[u];    g[u]=nume;}void spfa(){    while (!q.empty()) q.pop();    for (int i=1;i<=tot;i++) dis[i]=inf;    dis[1]=0;q.push(1);vis[1]=true;    while (!q.empty())    {        int head=q.front();q.pop();        for (int i=g[head];i;i=e[i].nxt)        {            int v=e[i].v;            if (dis[v]>dis[head]+e[i].w)            {                dis[v]=dis[head]+e[i].w;                if (!vis[v])                {                    vis[v]=true;                    q.push(v);                }            }        }        vis[head]=false;    }}int main(){    scanf("%d%d%d",&n,&m,&k);        for (int i=1;i<=n;i++)        for (int j=k;j>=0;j--)            v[i][j]=++tot;    for (int i=1;i<=m;i++)    {        scanf("%d%d%d",&x,&y,&z);        for (int j=k;j>=0;j--)        {            addedge(v[x][j],v[y][j],z);            addedge(v[y][j],v[x][j],z);        }        for (int j=k;j>=1;j--)        {            addedge(v[x][j],v[y][j-1],z/2);            addedge(v[y][j],v[x][j-1],z/2);        }    }    spfa();    for (int i=k;i>=0;i--)        ans=min(ans,dis[v[n][i]]);    printf("%d\n",ans);    return 0;}