#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int MAXN = 3000 + 1000;
const int MAXM = 4 * 100000 + 1000;
const int INF = 2147483647;

struct Edge
{
    int next, to, w;
}
e[MAXM];
int p[MAXN], head[MAXN], l = 2;

void addE(int a, int b, int c)
{
    e[l].next = p[a];
    e[l].to = b, e[l].w = c;
    p[a] = l++;
}

void ins2(int a, int b, int c)
{
    addE(a, b, c);
    addE(b, a, c);    
}

int S, T, totp;
int dis[MAXN];
int flow = 0;

bool bfs(int a, int b)
{
    static queue<int> q;
    memset(dis, 0, (totp + 2) * sizeof(dis[0]));
    dis[a] = 1, q.push(a);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i = p[x]; i; i = e[i].next)
            if(e[i].w > 0 && !dis[e[i].to])
                dis[e[i].to] = dis[x] + 1, q.push(e[i].to);
    }
    return dis[b];
}

int dfs(int x, int b, int s)
{
    if(x == b)
    {
        flow += s;
        return s;
    }
    int ret = 0;
    for(int &i = head[x]; i; i = e[i].next)
        if(e[i].w > 0 && dis[e[i].to] == dis[x] + 1)
        {
            int y = e[i].to, t = dfs(y, b, min(s, e[i].w));
            e[i].w -= t, e[i ^ 1].w += t;
            s -= t, ret += t;
            if(s <= 0) break;
        }
    return ret;
}

void dinic()
{
    flow = 0;
    while(bfs(S, T))
    {
        memcpy(head, p, (totp + 2) * sizeof(p[0]));
        while(dfs(S, T, INF));
    }
}

int n, m;
struct Relationship
{
    int x, y, w;    
}
edge[MAXM];
bool fin[MAXN];
int ans;

void init()
{
    ans = INF;
    memset(fin, 0, sizeof(fin));
}

void work()
{
    init();
    for(int i = 1; i <= m; i++)
        cin >> edge[i].x >> edge[i].y >> edge[i].w;
    int st = rand() % n + 1;
    fin[st] = true;
    for(int i = 1; i <= n; i++)
        if(!fin[i])
        {
            S = st, T = i, totp = n;
            memset(p, 0, (totp + 2) * sizeof(p[0])), l = 2;
            for(int j = 1; j <= m; j++)
                ins2(edge[j].x, edge[j].y, edge[j].w);
            dinic();
//            cout << flow << endl;
            ans = min(ans, flow);
        }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
//    freopen("1.in", "r", stdin);
//    freopen("1.out", "w", stdout);

    while(cin >> n >> m)
        work();
    
    
    return 0;
}