#include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define N 505

 int mp[N][N], vis[N], wage[N], combine[N], S, T, ans, mincut, m, n;

 void search() {

     memset(vis, , sizeof(vis));

     memset(wage, , sizeof(wage));

     S = T = -;

     int ma, index;

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

         ma = -INF;

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

             if(!vis[j] && !combine[j] && wage[j] > ma) {

                 ma = wage[j]; index = j;

             }

         }

         if(T == index) return ;

         vis[index] = ;

         S = T; T = index;

         mincut = ma;

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

             if(!vis[j] && !combine[j]) wage[j] += mp[T][j];

         }

     }

 }

 int Stoer_Wagner() {

     ans = INF;

     memset(combine, , sizeof(combine));

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

         search();

         combine[T] = ;

         if(ans > mincut) ans = mincut;

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

             mp[S][j] += mp[T][j];

             mp[j][S] += mp[j][T];

         }

     }

     return ans;

 }

 int main() {

     while(~scanf("%d%d", &n, &m)) {

         memset(mp, , sizeof(mp));

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

             int u, v, w;

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

             mp[u][v] += w;

             mp[v][u] += w;

         }

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

     }

     return ;

 }