#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1000000000;
typedef struct celula{
           int nod;
           celula *next;
           }*lista;
lista g[65],v;
int gin[65],gout[65],i,n,m,x,y,cost[65][65],cap[65][65],s,d,sol,tata[65],dist[65],coada[3600],st,en;
bool ok=1;

void muchie(int x, int y) {
     v=new celula; v->nod=x; v->next=g[y]; g[y]=v;
     v=new celula; v->nod=y; v->next=g[x]; g[x]=v;
}

void update(){
     int mmin=inf,aux=d;
     while (tata[aux]!=aux) {
                         mmin=min(mmin,cap[tata[aux]][aux]);
                         aux=tata[aux];
                         }
      aux=d; sol+=(mmin*dist[d]);
     while (tata[aux]!=aux) {
           cap[tata[aux]][aux]-=mmin;
           cap[aux][tata[aux]]+=mmin;
           aux=tata[aux];
           }
}

void getway(){
     int i; en=st=1; coada[1]=0;
     for (i=1; i<=n+1; ++i) { tata[i]=0; dist[i]=inf; }
     while (st<=en) {
           int nod=coada[st];
           for (lista p=g[nod]; p; p=p->next)
            if (cap[nod][p->nod]>0&&dist[p->nod]>dist[nod]+cost[nod][p->nod]) {
                 dist[p->nod]=dist[nod]+cost[nod][p->nod];
                 tata[p->nod]=nod;
                 ++en; coada[en]=p->nod;
                 }
            ++st;
            }
}

int main(void) {
    ifstream fin("traseu.in");
    ofstream fout("traseu.out");
    fin>>n>>m; s=0; d=n+1;
    for (i=1; i<=m; ++i) {
        fin>>x>>y>>cost[x][y]; sol+=cost[x][y]; cost[y][x]=-cost[x][y]; ++gout[x]; ++gin[y]; cap[x][y]=inf; muchie(x,y);
        }
    for (i=1; i<=n; ++i)
     if (gin[i]>gout[i]) { cap[s][i]=gin[i]-gout[i]; muchie(s,i); }
      else if (gout[i]>gin[i]) { cap[i][d]=gout[i]-gin[i]; muchie(i,d); }
    while (ok) {
          ok=0; getway();
          if (dist[d]!=inf) { ok=1; update(); }
          }
    fout<<sol;
  return(0);
}