#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 999999999
int N, M, in[63], out[63], C[63][63], F[63][63];
int sursa, dest, TT[63], D[63];
vector<pair<int, int> > G[63];

int BellmanFord() {
    queue<int> Q;
    bool InQueue[62];
    int i, j, p, q;
    for(i=0; i<=N+2; i++) {
         D[i]=INF; InQueue[i]=0;
    }
    D[sursa]=0; InQueue[sursa]=1;
    Q.push(sursa);
    while(!Q.empty()) {
         p=Q.front(); Q.pop(); InQueue[p]=0;
         for(vector<pair<int, int> >::iterator it=G[p].begin(); it!=G[p].end(); it++) {
              if(C[p][(*it).first]>F[p][(*it).first] && D[p]+(*it).second<D[(*it).first]) {
                   D[(*it).first]=D[p]+(*it).second;
                   TT[(*it).first]=p;
                   if(!InQueue[(*it).first]) {
                        InQueue[(*it).first]=1;
                        Q.push((*it).first);
                   }
              }
         }
    }
    if(D[dest]<INF) {
         int flow=INF;
         for(i=dest; i!=sursa; i=TT[i]) {
              flow=min(flow, C[TT[i]][i]-F[TT[i]][i]);
         }
         for(i=dest; i!=sursa; i=TT[i]) {
              F[TT[i]][i]+=flow;
              F[i][TT[i]]-=flow;
         }
         return D[dest]*flow;
    }
    return 0;
}

int main() {
    FILE *f1=fopen("traseu.in", "r"), *f2=fopen("traseu.out", "w");
    int i, j, p, q, c;
    long long sum=0;
    fscanf(f1, "%d%d", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d%d%d", &p, &q, &c);
         G[p+1].push_back(make_pair(q+1, c));
         sum+=c;
         G[q+1].push_back(make_pair(p+1, -c));
         out[p+1]++; in[q+1]++;
         C[p+1][q+1]=INF;
    }
    //sursa este nodul 1 si destinatia este nodul N+2
    for(i=2; i<=N+1; i++) {
         if(in[i]>out[i]) {
              //leg nodul i de sursa
              G[1].push_back(make_pair(i, 0));
              G[i].push_back(make_pair(1, 0));
              C[1][i]=in[i]-out[i];
         }
         else if(in[i]<out[i]) {
              //leg nodul i de destinatie
              G[N+2].push_back(make_pair(i, 0));
              G[i].push_back(make_pair(N+2, 0));
              C[i][N+2]=out[i]-in[i];
         }
    }
    sursa=1; dest=N+2;
    long long sol=0;
    int flow=1;
    while(flow) {
         flow=BellmanFord();
         sol+=flow;
    }
    fprintf(f2, "%lld\n", (long long)sum+sol);
    fclose(f1); fclose(f2);
    return 0;
}