分析：很明显的费用流，最重要的还是建图，首先确立源点和汇点，因为城市0为初始点，所以我定义s为源点，然后t为汇点，s-->0建边，流量为k，费用为0，因为不一定所有K都要用到，所以需要在0-->t建边，流量为K，费用为0，接下来就是拆点了。

1）、0-->i 建边，流量为1，费用为0-->i的最短路。

2）、i-->n+i 建边，流量为1，费用-inf ，这样可以保证所有城市都能遍历到。

3）、n+i-->j建边，流量为1，费用为i-->j的最短路。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn = 105;
const int maxm = 4050;
const int INF = 105000;
const int inf = 0x3f3f3f3f;
struct Node{int v,next,cap,cost;
}e[maxm * 10];
int Map[maxn][maxn];
int n,m,k,head[maxn<<1],dis[maxn<<1],mark[maxn<<1],path[maxn<<1],node[maxn<<1],num;
void add(int a,int b,int c,int d){e[num].v=b;e[num].cap=c;e[num].cost=d;e[num].next=head[a];head[a]=num++;e[num].v=a;e[num].cap=0;e[num].cost=-d;e[num].next=head[b];head[b]=num++;
}
int Mincost(int s,int t){int ans=0;queue<int>q;while(1){memset(dis,inf,sizeof(dis));memset(path,-1,sizeof(path));memset(node,-1,sizeof(node));q.push(s);mark[s]=1;dis[s]=0;while(!q.empty()){int u=q.front();q.pop();mark[u]=0;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].v;int cost=e[i].cost;if(dis[v]>dis[u]+cost && e[i].cap>0){dis[v]=dis[u]+cost;if(!mark[v]){mark[v]=1;q.push(v);}path[v]=u;node[v]=i;}}}// printf("%d---",dis[t]);if(dis[t]>=inf) break;int flow=inf;int now=t;while(path[now]!=-1){int ff;ff=node[now];flow=min(flow,e[ff].cap);now=path[now];}ans+=dis[t]*flow;now=t;while(path[now]!=-1){e[node[now]].cap-=flow;e[node[now]^1].cap+=flow;now=path[now];}// printf("%d\n",flow);}return ans;
}
void floyd(){for(int k=0;k<=n;k++){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){Map[i][j]=min(Map[i][k]+Map[k][j],Map[i][j]);}}}
}
int main(){while(~scanf("%d %d %d",&n,&m,&k) && (n+m+k)){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){Map[i][j]=inf;}}for(int i=0;i<m;i++){int a,b,c;scanf("%d %d %d",&a,&b,&c);Map[a][b]=Map[b][a]=min(Map[a][b],c);}floyd();int ss=0;int s=2*n+1;int t=2*n+2;int ans=INF;num=0;memset(head,-1,sizeof(head));add(s,ss,k,0);add(ss,t,k,0);for(int i=1;i<=n;i++){if(Map[0][i]<inf){add(ss,i,1,Map[0][i]);add(i+n,t,1,Map[i][0]);}add(i,i+n,1,-INF);for(int j=i+1;j<=n;j++){if(Map[i][j]<inf)add(i+n,j,1,Map[i][j]);}}ans=Mincost(s,t)+n*INF;printf("%d\n",ans);}
}