#include<iostream>
 #include<queue>
 #include<cstdio>
 #include<cstring>
 using namespace std;
 ;
 struct node{
     int from,to,next,dis,bro;
 }edge[N*];
 ,dis[N],ans=,last[N];
 ],in[N],can=true;
 inline void unite(int x,int y,int w,int b)
 {
     edge[s].from=x;
     edge[s].bro=b;
     edge[s].to=y;
     edge[s].dis=w;
     edge[s].next=head[x];
     head[x]=s;
     return;
 }
 inline ;return;}
 inline void dfs(int step,int res)
 {
     if(step==k)
     {
         ans=min(ans,res);
         return;
     }
     if(!can) return;
     node store[N*];
     ;i<=s;i++) store[i]=edge[i];
     ;
     ;u<=k;u++) )
     {
         used[u]=;
         ) ;i<=s;i++) edge[i]=store[i];
         ;
         queue<int> Q;
         memset(dis,,sizeof(dis));
         memset(last,,sizeof(last));
         ];
         dis[u]=;
         Q.push(u);
         while(!Q.empty())
         {
             int f=Q.front();
             Q.pop();
             ;
             for(int i=head[f];i;i=edge[i].next) if(edge[i].dis+dis[f]<dis[edge[i].to])
             {
                 dis[edge[i].to]=edge[i].dis+dis[f];
                 last[edge[i].to]=i;
                 if(!in[edge[i].to])
                 {
                     Q.push(edge[i].to);
                     ;
                 }
             }
         }
         ]) can=;
         else
         {
             ;
             )
             {
                 del(last[p]);
                 del(edge[last[p]].bro);
                 p=edge[last[p]].from;
             }
             dfs(step+,res+dis[n-u+]);
         }
         used[u]=;
     }
     return;
 }
 int main()
 {
     int x,y,w;
     scanf("%d%d%d",&n,&m,&k);
     ;i<=m;i++)
     {
         scanf("%d%d%d",&x,&y,&w);
         s++;unite(x,y,w,s+);
         s++;unite(y,x,w,s-);
     }
     memset(used,,sizeof(used));
     dfs(,);
     if(!can) printf("-1\n");
     else printf("%d\n",ans);
     ;
 }