#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

#define Pe pair <int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream cin ("traseu.in");
ofstream cout ("traseu.out");

const int MaxN = 65, Inf = 0x3f3f3f3f;

class m_node {
public:
  int nd, dist;

  m_node (int _nd = 0, int _dist = 0) {
    nd = _nd;
    dist = _dist;
  }

  inline bool operator < (const m_node &other) const {
    return dist > other.dist;
  }
};

vector <Pe> G[MaxN];
priority_queue <m_node> PrioQ;
int n, m, Source, Destination, Ans;
int Flow[MaxN][MaxN], Capacity[MaxN][MaxN], InDeg[MaxN], OutDeg[MaxN], father[MaxN], Dist[MaxN];

inline void ClearPQ() {
  while (PrioQ.size()) {
    PrioQ.pop();
  }
}

bool Dijkstra() {
  ClearPQ();
  memset(father, 0, sizeof father);
  memset(Dist, Inf, sizeof Dist);
  father[Source] = -1;
  Dist[Source] = 0;
  PrioQ.push(m_node(Source, 0));

  while (PrioQ.size()) {
    m_node top = PrioQ.top();
    PrioQ.pop();

    if (top.dist > Dist[top.nd]) {
      continue;
    }

    for (auto nxt: G[top.nd]) {
      int NewDist = top.dist + nxt.se;
      if (NewDist < Dist[nxt.fi] and Capacity[top.nd][nxt.fi] - Flow[top.nd][nxt.fi]) {
        Dist[nxt.fi] = NewDist;
        father[nxt.fi] = top.nd;
        PrioQ.push(m_node(nxt.fi, Dist[nxt.fi]));

        if (nxt.fi == Destination) {
          return true;
        }
      }
    }
  }

  return false;
}

inline int CalcQty(int node = Destination) {
  int ans = Inf;
  while (father[node] != -1) {
    int parent = father[node];
    ans = min(ans, Capacity[parent][node] - Flow[parent][node]);
    node = parent;
  }

  return ans;
}

inline void FlowUpdate(int Qty, int node = Destination) {
  while (father[node] != -1) {
    int parent = father[node];
    Flow[parent][node] += (Flow[parent][node] == Inf) ? 0 : Qty;
    Flow[node][parent] -= (Flow[parent][node] == Inf) ? 0 : Qty;
    node = parent;
  }
}

int main() {
  cin >> n >> m;
  Destination = n + 1;
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    ++InDeg[b];
    ++OutDeg[a];
    G[a].push_back(mp(b, c));
    G[b].push_back(mp(a, -c));
    Capacity[a][b] = Inf;
    Ans += c;
  }

  for (int i = 1; i <= n; ++i) {
    if (InDeg[i] < OutDeg[i]) {
      G[i].push_back(mp(Destination, 0));
      Capacity[i][Destination] = OutDeg[i] - InDeg[i];
    }
    else if (OutDeg[i] < InDeg[i]) {
      G[Source].push_back(mp(i, 0));
      Capacity[Source][i] = InDeg[i] - OutDeg[i];
    }
  }

  while (Dijkstra()) {
    int Qty = CalcQty();
    FlowUpdate(Qty);
    Ans += Qty * Dist[Destination];
  }

  cout << Ans << '\n';
  return 0;
}