#include <iostream>

#include <cstdio>

#include <cstring>

#include <ext/pb_ds/priority_queue.hpp>

typedef long long ll;

typedef __gnu_pbds::priority_queue<std::pair<int, int>, std::less<std::pair<int, int> >, __gnu_pbds::binomial_heap_tag >pq;

struct Edge {int from, to, nxt, val;};

const int maxn = 3e3 + ;

const int maxm = 4e5 + ;

const int inf = ;

int n, r;

bool vis[maxn], bin[maxn];

Edge e[maxm *  + ];

int head[maxn], id[maxn][maxn], esz;

inline ll read() {

  int x = , f = ; char ch = getchar();

  while(ch < '' || ch > '') {if(ch == '-')f = -; ch = getchar();}

  while(ch >= '' && ch <= '') {x = x *  + ch - ''; ch = getchar();}

  return x * f;

}

inline void add_edge(int from, int to, int val) {

  if(id[from][to] == -) {

    e[esz].from = from, e[esz].to = to, e[esz].val = val, e[esz].nxt = head[from];

    id[from][to] = esz; head[from] = esz++;

  } else {

    e[id[from][to]].val += val;

  }

}

inline void init() {

  memset(bin, false, sizeof(bin));

  memset(head, -, sizeof(head));

  memset(id, -, sizeof(id));

  esz = ;

}

pq que;

pq::point_iterator it[maxn];

inline int contract(int &s, int &t) {          // Find s,t

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

  int i, j, k, mincut, maxc;

  while(!que.empty()) que.pop();

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

    if(!bin[i])it[i] = que.push(std::make_pair(, i));

    else it[i] = nullptr;

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

    k = -; maxc = -;

    if(que.empty()) return mincut;

    k = que.top().second, maxc = que.top().first; que.pop();

    s = t;  t = k; mincut = maxc; vis[k] = true;

    for(j = head[k]; ~j; j = e[j].nxt) {

      int v = e[j].to, w = e[j].val;

      if(!bin[v] && !vis[v]) {

        que.modify(it[v], std::make_pair((it[v]->first) + w, v));

      }

    }

  }

  return mincut;

}

inline int Stoer_Wagner() {

  int mincut, i, j, s, t, ans;

  for(mincut = inf, i = ; i < n; i++) {

    ans = contract(s, t);

    bin[t] = true;

    if(mincut > ans) mincut = ans;

    if(mincut == )return ;

    for(j = ; j <= n; j++) if(!bin[j]) {

        if(id[j][t] == -)continue;

        if(id[s][j] == -)add_edge(s, j, e[id[j][t]].val);

        else e[id[s][j]].val += e[id[j][t]].val;

        if(id[j][s] == -)add_edge(j, s, e[id[j][t]].val);

        else e[id[j][s]].val += e[id[j][t]].val;

      }

  }

  return mincut;

}

int main() {

  int m;

  while(scanf("%d%d", &n, &m) != -) {

    init();

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

      int a, b, c;

      a = read(), b = read(), c = read();

      add_edge(a, b, c); add_edge(b, a, c);

    }

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

  }

  return ;

}