#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 555

#define inf 1<<30

int v[MAXN],dist[MAXN];

int map[MAXN][MAXN];

bool vis[MAXN];

int n,m,xx;

//结点下标从0开始！！！！！！！！！

//求全局最小割的Stoer_Wanger算法

int Stoer_Wanger(int n)

{

    int res=inf;

    for(int i=;i<n;i++)v[i]=i;

    while(n>){

        int k=,pre=;//pre用来表示之前加入A集合的点，我们每次都以0点为第一个加入A集合的点

        memset(vis,false,sizeof(vis));

        memset(dist,,sizeof(dist));

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

            k=-;

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

                if(!vis[v[j]]){

                    dist[v[j]]+=map[v[pre]][v[j]];//dis数组用来表示该点与A集合中所有点之间的边的长度之和

                    if(k==-||dist[v[k]]<dist[v[j]]){

                        k=j;

                    }

                }

            }

            vis[v[k]]=true;

            if(i==n-){

                res=min(res,dist[v[k]]);

                //将该点合并到pre上，相应的边权就要合并

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

                    map[v[pre]][v[j]]+=map[v[j]][v[k]];

                    map[v[j]][v[pre]]+=map[v[j]][v[k]];

                }

                v[k]=v[--n];//删除最后一个点

            }

            pre=k;

        }

    }

    return res;

}

int main()

{

    int u,v,w;

    while()

    {

        scanf("%d%d%d",&n,&m,&xx);

        if(n==&&m==&&xx==) break;

        memset(map,,sizeof(map));

        while(m--){

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

            u--,v--;

            map[u][v]+=w;

            map[v][u]+=w;

        }

        int ans=Stoer_Wanger(n);

        printf("%d\n",ans);

    }

    return ;

}