#3RE 为什么题目M<=1000，我M=1005会RE，M=1500就不会RE了，是我哪里没弄懂吗

#include<bits/stdc++.h>
using namespace std;
const int maxn=55,maxm=1e3+5,maxk=55,inf=0x3f3f3f3f;
int head[maxn*maxk],cnt=-1,dis[maxn*maxk];
bool used[2*maxm*maxk];
struct edge
{
    int ed,dis,next;
}e[maxm*2*maxk];

struct node
{
    int p,dis;
    bool operator<(const node& h)const{
        return dis>h.dis;
    }
};
priority_queue<node> q;
void add_edge(int st,int ed,int dis)
{
    e[++cnt].ed=ed;
    e[cnt].dis=dis;
    e[cnt].next=head[st];
    head[st]=cnt;
}

void dijkstra()
{
    dis[1]=0;
    q.push((node){1,0});
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        int u=now.p;
        if(dis[u]!=now.dis)
            continue;
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].ed;
            if(dis[v]>dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                q.push((node){v,dis[v]});
            }
        }
    }
}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n*(k+1);i++)
        head[i]=-1,dis[i]=inf;
    for(int i=1;i<=m;i++)
    {
        int u,v,val;
        scanf("%d%d%d",&u,&v,&val);
        add_edge(u,v,val);
        add_edge(v,u,val);
        for(int j=1;j<=k;j++){
            add_edge(u+n*j,v+n*j,val);
            add_edge(v+n*j,u+n*j,val);
            add_edge(u+n*j-n,v+n*j,val/2);
            add_edge(v+n*j-n,u+n*j,val/2);
        }
    }
    dijkstra();
    int res=dis[n];
    for(int i=1;i<=k;i++)
        res=min(res,dis[n+i*n]);
    printf("%d\n",res);
    return 0;
}