#include<bits/stdc++.h>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 const int maxv = ;

 typedef pair<int,int> P;

 struct edge{

     int to,cap,cost,rev;

 };

 int V;

 vector<edge> g[maxv];

 int h[maxv];

 int dist[maxv];

 int prevv[maxv],preve[maxv];

 void addedge(int from,int to,int cap,int cost){

     g[from].push_back(edge{to,cap,cost,g[to].size()});

     g[to].push_back((edge{from,,-cost,g[from].size()-}));

 }

 int solve(int s,int t,int f){

     int res = ;

     memset(h,,sizeof(h)) ;

     while(f > ){

         priority_queue<P,vector<P>,greater<P> > que;

         memset(dist,inf,sizeof(dist));

         dist[s] = ;

         que.push(P(,s));

         while(!que.empty()){

             P p = que.top();

             que.pop();

             int v = p.second;

             if(dist[v] < p.first)

                 continue;

             for(int i = ;i<g[v].size();i++){

                 edge &e = g[v][i] ;

                 if(e.cap> && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){

                     dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];

                     prevv[e.to] = v;

                     preve[e.to] = i;

                     que.push(P(dist[e.to],e.to));

                 }

             }

         }

         if(dist[t] == inf)

             return -;

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

             h[i] += dist[i];

         int d = f;

         for(int v = t;v!=s;v=prevv[v])

             d = min(d,g[prevv[v]][preve[v]].cap);

         f -= d;

         res += d*h[t];

         for(int v = t;v!=s;v = prevv[v]){

             edge &e = g[prevv[v]][preve[v]];

             e.cap -= d;

             g[v][e.rev].cap += d;

         }

     }

     return res;

 }

 int mp[][];

 int main(){

     int n,m,k;

     while(scanf("%d%d%d",&n,&m,&k)){

         if(!n && !m && !k)

             break;

         V = *n+;

         int s = *n+,t = *n+;

         for(int i = ;i<*n+;i++)

             g[i].clear();

         memset(mp,inf,sizeof(mp));

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

             mp[i][i] = ;

         int u,v,w;

         while(m--){

             scanf("%d%d%d",&u,&v,&w);

             mp[u][v] = mp[v][u] = min(mp[u][v],w);

         }

         for(int k = ;k<=n;k++)

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

                 for(int j = ;j<=n;j++)

                     mp[i][j] = min(mp[i][j],mp[i][k]+mp[k][j]);

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

             addedge(,i,,mp[][i]);

             addedge(i+n,t,,mp[][i]);

             addedge(i,i+n,,-);

             for(int j = i+;j<=n;j++){

                 if(mp[i][j] != inf)

                     addedge(i+n,j,k,mp[i][j]);

             }

         }

         addedge(s,,k,);

         addedge(,t,k,);

         cout << solve(s,t,k)+n* << endl;

     }

     return ;

 }