#include <bits/stdc++.h>
#define MAXN 3005
#define MAXM 200005
#define ll long long
#define Inf 0x3f3f3f3f

using namespace std;

int n,m,s,t,cnt;
int maze[MAXN][MAXN];
int cur[MAXN],head[MAXN],deep[MAXN],head2[MAXN];
ll minnnn;

struct node{
int to, next;
ll dis;
}edge[MAXM],edge2[MAXM];

void addedge(int u, int v, ll w)
{
    edge[++cnt].to = v;
    edge[cnt].dis = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void addedge2(int u, int v, ll w)
{
    edge2[++cnt].to = v;
    edge2[cnt].dis = w;
    edge2[cnt].next = head2[u];
    head2[u] = cnt;
}

void init()
{
    cnt=-1;
    minnnn = 0x3f3f3f3f3f3f3f3f;
    memset(head,-1,sizeof head);
    memset(head2,-1,sizeof head2);
    memset(maze,0,sizeof maze);
}

ll dfs(int now, ll minn)
{
    ll flow, sum = 0;                  //flow:后方路线的流量   sum：当前节点的总流量
    if(now == t) return minn;
    for(int i = cur[now]; (i!=-1)&&minn; i=edge[i].next)
    {
        cur[now] = i;                     //当前弧优化
        int ts = edge[i].to;
        if((deep[ts] == deep[now]+1) && edge[i].dis>0)
        {
            flow = dfs(ts,min(minn,edge[i].dis));
            if(flow == 0) deep[ts] = -1;
            edge[i].dis -= flow;
            edge[i^1].dis += flow;
            sum += flow;
            minn -= flow;
        }
    }
    return sum;
}

bool bfs()      //BFS分层
{
    memset(deep,-1,sizeof(deep));
    queue<int> que;
    que.push(s);
    deep[s] = 0;
    cur[s] = head[s];
    while(!que.empty())
    {
        int v1 = que.front();
        que.pop();
        for(int i=head[v1]; i!=-1; i=edge[i].next)
        {
            int ts = edge[i].to;
            if(deep[ts] == -1 && edge[i].dis>0)
            {
                deep[ts] = deep[v1] + 1;
                que.push(ts);
                cur[ts] = head[ts];
                if(ts == t) return 1;
            }
        }
    }
    return(deep[t]+1);          //t节点层次为-1（不可达），跳出
}

void build()
{
    cnt=-1;
    memset(cur,0,sizeof cur);
    memset(head,-1,sizeof head);
    for(int now=1; now<=n; now++)
    {
        for(int i=head2[now]; i!=-1; i=edge2[i].next)
        {
            addedge(now,edge2[i].to,edge2[i].dis);
            addedge(edge2[i].to,now,edge2[i].dis);
        }
    }
}

int main()
{
    while(cin >> n >> m)
    {
        init();
        int x,y,z;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            maze[x][y] += z;
            maze[y][x] += z;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                if(maze[i][j])
                    addedge2(i,j,maze[i][j]);
            }
        }

        s=1;
        for(int i=2; i<=n; i++)
        {
            build();
            ll sum = 0;
            t=i;
            while(bfs())
                sum += dfs(s,Inf);
            minnnn = min(minnnn,sum);
        }

        printf("%lld\n",minnnn);
    }

    return 0;
}