g[now][id].c-=temp;
g[to][back[to]].c+=temp;
return temp;
}
int ek()
{
int ans=0;
for(int i=0;i
ans+=d[i][i+1];
}
ans+=d[0][n];
while(spfa())
{
ans+=dfs()*way[end];
}
return ans;
}
int main()
{
while(cin>>n>>m>>k)
{
if(!m && !n && !k) return 0;
for(int i=0;i
g[i].clear();
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
d[i][j]=inf;
}
for(int i=0;i<=n;i++)
{
d[i][i]=0;
}
int now,to,len;
for(int i=1;i<=m;i++)
{
cin>>now>>to>>len;
d[now][to]=d[to][now]=min(d[now][to],len);
}
floyd();
link(0,1,0,d[0][1],1);
for(int i=2;i<=n;i++)
{
link(0,i,1,d[0][i]);
}
for(int i=1;i
link(i+add,end,1,d[i][0]);
}
link(n+add,end,0,d[n][0],1);
link(0,end,inf,0);
link(head,0,k-1,0,1);
for(int i=1;i<=n;i++)
{
link(i+add,i+1,0,d[i][i+1],1);
for(int j=i+2;j<=n;j++)
{
link(i+add,j,1,d[i][j]);
}
}
cout<
return 0;
}