/**************************************************************

    Problem: 2662

    User: zhangheran

    Language: C++

    Result: Accepted

    Time:12 ms

    Memory:1356 kb

****************************************************************/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int n,m,k;

struct data{

    int u;int v;int value;int next;

}edge[];int alist[];

int cnt;

void add(int u,int v,int value)

{

    edge[cnt].v=v;

    edge[cnt].u=u;

    edge[cnt].value=value;

    edge[cnt].next=alist[u];

    alist[u]=cnt++;

    return ;

}

struct node{int u;int v;};

queue<node> q;

int d[][];

bool ins[][];

void spfa()

{

    d[][]=;

    ins[][]=true;

    q.push((node){,});

    while(!q.empty())

    {

        node x=q.front();

        q.pop();

        ins[x.u][x.v]=false;

        int next=alist[x.v];

        while(next!=-)

        {

            int v=edge[next].v;

            if(d[x.u][v]>d[x.u][x.v]+edge[next].value){

                d[x.u][v]=d[x.u][x.v]+edge[next].value;

                if(!ins[x.u][v])

                    ins[x.u][v]=true,

                    q.push((node{x.u,v}));

            }

            next=edge[next].next;

        }

        if(x.u<k){

            int next=alist[x.v];

            while(next!=-){

                int v=edge[next].v;

                if(d[x.u+][v]>d[x.u][x.v]+edge[next].value/){

                    d[x.u+][v]=d[x.u][x.v]+edge[next].value/;

                    if(!ins[x.u+][v])

                        ins[x.u+][v]=true,

                        q.push((node){x.u+,v});

                }

                next=edge[next].next;

            }

        }

    }

}

int u,v,value;

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    memset(d,0x3f3f3f3f,sizeof(d));

    memset(alist,-,sizeof(alist));

    for(int i=;i<=m;i++)

        scanf("%d%d%d",&u,&v,&value),

        add(u,v,value),

        add(v,u,value);

    spfa();

    int minn=0x3f3f3f3f;

    for(int i=;i<=k;i++) minn=min(minn,d[i][n]);

    printf("%d",minn);

    return ;

}