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

using namespace std;

int n, m, sum, gi[65], go[65], edg[65][65];

void read(){
  ifstream in("traseu.in");

  in >> n >> m;

  for(int i = 1; i <= m; ++i){
    int x, y;
    in >> x >> y;
    in >> edg[x][y];
    sum += edg[x][y];
    ++gi[x];
    ++go[y];
  }
}

int bcost[65][65];

void roy_floyd(){
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      bcost[i][j] = edg[i][j];

  for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j)if(bcost[i][k] && bcost[k][j])
        if((bcost[i][j] == 0 && i != j) || bcost[i][j] > bcost[i][k] + bcost[k][j])
          bcost[i][j] = bcost[i][k] + bcost[k][j];
}

int source, dest, cost[65][65], cap[65][65], fl[65][65];

void build_network(){
  source = 0;
  dest = n + 1;
  for(int i = 1; i <= n; ++i)
    if(go[i] > gi[i]){
      cap[source][i] = go[i] - gi[i];
      for(int j = 1; j <= n; ++j)
        if(gi[j] > go[j] && bcost[i][j]){
          cap[i][j] = 1337;
          cost[i][j] = bcost[i][j];
          cost[j][i] = -bcost[i][j];
        }
    }
    else if(gi[i] > go[i])
      cap[i][dest] = gi[i] - go[i];
}

int dad[65], ds[65];

int blm(){
  memset(dad, 0, sizeof(dad));
  memset(ds, 1337, sizeof(ds));

  queue<int> q;
  q.push(0);
  ds[0] = 0;

  while(!q.empty()){
    int now = q.front();
    q.pop();
    for(int i = 1; i <= n + 1; ++i)
      if(cap[now][i] - fl[now][i])
        if(ds[i] > ds[now] + cost[now][i]){
          q.push(i);
          ds[i] = ds[now] + cost[now][i];
          dad[i] = now;
        }
  }

  if(ds[dest] <= 5e8)
    return 1;
  return 0;
}

int ans;

void mincflow(){
  int c_flow;

  while(blm()){
    c_flow = 1337;
    for(int i = dest; i != source; i = dad[i])
      c_flow = min(c_flow, cap[dad[i]][i] - fl[dad[i]][i]);
    for(int i = dest; i != source; i = dad[i]){
      ans += c_flow * cost[dad[i]][i];
      fl[dad[i]][i] += c_flow;
      fl[i][dad[i]] -= c_flow;
    }
  }
}

void solve(){
  roy_floyd();
  build_network();
  mincflow();

  ans += sum;
}

void write(){
  ofstream out("traseu.out");

  out << ans;
}

int main(){
  read();
  solve();
  write();

  return 0;
}