#include<iostream>

using namespace std;

const int MAXN = 512;
const int inf = 0x7f7f7f7f;

bool vis[MAXN];
int u, v, w, n, m, ver[MAXN], dis[MAXN], map[MAXN][MAXN];

int stoer_wagner(int n)
{
	int s, t, cnt = inf;
	
	for (int i = 0; n - i > 0; i++)
		ver[i] = i;
	
	while (n > 1)
	{
		vis[0] = true;
		for (int i = 1; n - i > 0; i++)
		{
			vis[i] = false;
			dis[i] = map[ver[0]][ver[i]];
		}
		s = 0;
		for (int i = 1; n - i > 0; i++)
		{
			t = -1;
			for (int j = 1; n - j > 0; j++)
				if (!vis[j])
				{
					if (t == -1 || dis[j] > dis[t]) t = j;
				}
			if (i == n - 1)
			{
				cnt = min(cnt, dis[t]);
				for (int j = 0; n - j > 0; j++)
				{
					map[ver[s]][ver[j]] += map[ver[t]][ver[j]];
					map[ver[j]][ver[s]] += map[ver[j]][ver[t]];
				}
				ver[t] = ver[--n];
			}
			else
			{
				vis[s = t] = true;
				for (int j = 1; n - j > 0; j++)
					if (!vis[j])
					{
						dis[j] += map[ver[t]][ver[j]];
					}
			}
		}
	}
	return cnt;
}
int main()
{
	while (scanf("%d %d", &n, &m) != EOF)
	{
		memset(map, 0, sizeof(map));
		
		while (m--)
		{
			scanf("%d %d %d", &u, &v, &w);
			map[u][v] += w;
			map[v][u] += w;
		}
		
		printf("%d\n", stoer_wagner(n));
	}
	return 0;
}