#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cstdlib>

 #include<ctime>

 #include<vector>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define LL long long

 const int maxn=;

 const int inf=;

 struct node{

     int x,y,next;

     int v;

 }e[maxn*];

 int linkk[maxn],len=;

 int n,m,k;

 LL d[maxn][];

 void insert(int x,int y,int v){

     e[++len].y=y;

     e[len].x=x;

     e[len].next=linkk[x];

     linkk[x]=len;

     e[len].v=v;

 }

 void init(){

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

     int x,y,v;

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

         scanf("%d%d%d",&x,&y,&v);

         insert(x,y,v);insert(y,x,v);

     }

 }

 struct bian{

     int x,k;

     LL w;

     bian(int a,int b,LL c){x=a,k=b,w=c;}

     bool operator>(const bian& b)const{

         return w>b.w;

     }

 };

 priority_queue<bian,vector<bian>,greater<bian> > q;

 void dij(){

     memset(d,,sizeof(d));

     for(int i=;i<=k;i++)d[][i]=;

     q.push(bian(,,));

     while(!q.empty()){

         bian tmp=q.top();

         q.pop();

         int x=tmp.x;

         int p=tmp.k;

         LL w=tmp.w;

         for(int i=linkk[x];i;i=e[i].next){

             if(p<k&&w<d[e[i].y][p+]){

                 d[e[i].y][p+]=w;

                 q.push(bian(e[i].y,p+,w));

             }

             if(w+e[i].v<d[e[i].y][p]){

                 d[e[i].y][p]=w+e[i].v;

                 q.push(bian(e[i].y,p,d[e[i].y][p]));

             }

         }

     }

 }

 void work(){

     dij();

     cout<<d[n][k]<<endl;

 }

 int main(){

     init();

     work();

 }