//minamoto

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,M=,K=;

 struct node{

     int x,cnt,dis;

     node(){}

     node(int x,int cnt,int dis):x(x),cnt(cnt),dis(dis){}

     inline bool operator <(const node b)const

     {return cnt!=b.cnt?cnt>b.cnt:dis>b.dis;}

 };

 priority_queue<node> q;

 int vis[N][K],dis[N][K];

 int head[N],Next[M],ver[M],edge[M],tot;

 int n,m,k;

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;

     ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=e;

 }

 void dijkstra(){

     memset(dis,0x3f,sizeof(dis));

     memset(vis,,sizeof(vis));

     q.push(node(,,)),dis[][]=;

     while(!q.empty()){

         int u=q.top().x,cnt=q.top().cnt;q.pop();

         if(vis[u][cnt]) continue;

         vis[u][cnt]=;

         for(int i=head[u];i;i=Next[i]){

             int v=ver[i];

             if(dis[v][cnt]>dis[u][cnt]+edge[i]){

                 dis[v][cnt]=dis[u][cnt]+edge[i];

                 q.push(node(v,cnt,dis[v][cnt]));

             }

             if(cnt+<=k&&dis[v][cnt+]>dis[u][cnt]){

                 dis[v][cnt+]=dis[u][cnt];

                 q.push(node(v,cnt+,dis[v][cnt+]));

             }

         }

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read(),k=read();

     for(int i=,u,v,e;i<=m;++i)

     u=read(),v=read(),e=read(),add(u,v,e);

     dijkstra();

     printf("%d\n",dis[n][k]);

     return ;

 }