#include <fstream> #include <queue>   using namespace std;   ifstream fin("traseu.in"); ofstream fout("traseu.out");   const int inf= 1<<30; const int nmax= 60;   int in[nmax+1], out[nmax+1]; int cst[nmax+2][nmax+2], cpc[nmax+2][nmax+2]; vector <int> g[nmax+2];   bool inq[nmax+2]; queue <int> q; int bf[nmax+2], p[nmax+2];   int bellmanford(int n){     int src= 0, dest= n+1;     for (int i= 1; i<=n+1; ++i){         bf[i]= inf-1; p[i]= -1;     }     q.push(src); inq[src]= 1;       while (!q.empty()){         int x= q.front();         q.pop(); inq[x]= 0;         for (vector <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it){             if (cpc[x][*it]>0&& bf[*it]>bf[x]+cst[x][*it]){                 bf[*it]= bf[x]+cst[x][*it];                 p[*it]= x;                 if (inq[*it]==0){                     q.push(*it); inq[*it]= 1;                 }             }         }     }       return p[dest]!=-1; }   int main(){     int n, m;     fin>>n>>m;     for (int i= 1; i<=n; ++i){         for (int j= 1; j<=n; ++j){             if (i!=j){                 cst[i][j]= inf-1;             }         }     }     int sol= 0;     for (int i= 1; i<=m; ++i){         int x, y;         fin>>x>>y;         fin>>cst[x][y];         sol+= cst[x][y];         ++out[x]; ++in[y];     }       for (int i= 1; i<=n; ++i){         for (int j= 1; j<=n; ++j){             if (j!=i){                 for (int k= 1; k<=n; ++k){                     if (k!=i&& k!=j&& cst[j][k]>cst[j][i]+cst[i][k]){                         cst[j][k]= cst[j][i]+cst[i][k];                     }                 }             }         }     }       int src= 0, dest= n+1;     for (int i= 1; i<=n; ++i){         if (in[i]>out[i]){             g[i].push_back(src); g[src].push_back(i);              cpc[src][i]= in[i]-out[i];          }else if (in[i]<out[i]){             g[i].push_back(dest); g[dest].push_back(i);             cpc[i][dest]= out[i]-in[i];         }     }     for (int i= 1; i<=n; ++i){         for (int j= 1; j<=n; ++j){             if (in[i]>out[i]&& in[j]<out[j]){                 g[i].push_back(j); g[j].push_back(i);                 cpc[i][j]= inf;                 cst[j][i]= -cst[i][j];             }         }     }       while (bellmanford(n)){         int mxf= inf;         for (int i= dest; i!=src; i= p[i]){             if (mxf>cpc[p[i]][i]){                 mxf= cpc[p[i]][i];             }         }         sol+= mxf*bf[dest];         for (int i= dest; i!=src; i= p[i]){             cpc[p[i]][i]-= mxf;             cpc[i][p[i]]+= mxf;         }     }       fout<<sol<<"\n";     return 0; }