/**

  * Uva

  * Problem#1658

  * Accepted

  */

 #include<iostream>

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<cstdlib>

 #include<fstream>

 #include<sstream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #include<stack>

 using namespace std;

 typedef bool boolean;

 #define INF 0xfffffff

 #define smin(a, b) a = min(a, b)

 #define smax(a, b) a = max(a, b)

 template<typename T>

 inline boolean readInteger(T& u){

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-' && ~x);

     if(x == -){

         return false;

     }

     if(x == '-'){

         x = getchar();

         aFlag = -;

     }

     for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');

     ungetc(x, stdin);

     u *= aFlag;

     return true;

 }

 ///map template starts

 typedef class Edge{

     public:

         int end;

         int next;

         int cap;

         int flow;

         int cost;

         Edge(const int end = , const int next = , const int cap = , const int flow = , const int cost = ):end(end), next(next), cap(cap), flow(flow), cost(cost){}

 }Edge;

 typedef class MapManager{

     public:

         int ce;

         int *h;

         Edge *edge;

         MapManager(){}

         MapManager(int points, int limit):ce(){

             h = new int[(const int)(points + )];

             edge = new Edge[(const int)(limit + )];

             memset(h, , sizeof(int) * (points + ));

         }

         inline void addEdge(int from, int end, int cap, int flow, int cost){

             edge[++ce] = Edge(end, h[from], cap, flow, cost);

             h[from] = ce;

         }

         inline void addDoubleEdge(int from, int end, int cap, int cost){

             addEdge(from, end, cap, , cost);

             addEdge(end, from, cap, cap, -cost);

         }

         Edge& operator [](int pos){

             return edge[pos];

         }

         inline int reverse(int pos){

             return (pos & ) ? (pos + ) : (pos - );

         }

         inline void clean(){

             delete[] h;

             delete[] edge;

             ce = ;

         }

 }MapManager;

 #define m_begin(g, i) (g).h[(i)]

 /// map template ends

 int n, m;

 MapManager g;

 inline boolean init(){

     if(!readInteger(n))    return false;

     readInteger(m);

     g = MapManager(n * , m *  + n * );

     for(int i = , a, b, w; i <= m; i++){

         readInteger(a);

         readInteger(b);

         readInteger(w);

         g.addDoubleEdge(a + n, b, , w);

     }

     for(int i = ; i <= n; i++){            //拆点

         g.addDoubleEdge(i, i + n, , );

     }

     return true;

 }

 int* dis;

 boolean* visited;

 int* last;

 int* laste;

 int* mflow;

 int cost;

 int s, t;

 queue<int> que;

 int sizee;

 inline void spfa(){

     memset(dis, 0x7f, sizeof(int) * (sizee));

     memset(visited, false, sizeof(boolean) * (sizee));

     que.push(s);

     last[s] = ;

     dis[s] = ;

     laste[s] = ;

     mflow[s] = INF;

     visited[s] = true;

     while(!que.empty()){

         int e = que.front();

         que.pop();

         visited[e] = false;

         for(int i = m_begin(g, e); i != ; i = g[i].next){

             int &eu = g[i].end;

             if(dis[e] + g[i].cost < dis[eu] && g[i].flow < g[i].cap){

                 dis[eu] = dis[e] + g[i].cost;

                 last[eu] = e;

                 laste[eu] = i;

                 mflow[eu] = min(g[i].cap - g[i].flow, mflow[e]);

                 if(!visited[eu] && eu != t){

                     que.push(eu);

                     visited[eu] = true;

                 }

             }

         }

     }

     for(int i = t; i != s; i = last[i]){

         g[laste[i]].flow += mflow[t];

         g[g.reverse(laste[i])].flow -= mflow[t];

         cost += mflow[t] * g[laste[i]].cost;

     }

 }

 inline void minCostFlow(){

     s =  + n, t = n, sizee =  * n + ;

     dis = new int[(const int)(sizee)];

     visited = new boolean[(const int)(sizee)];

     last = new int[(const int)(sizee)];

     laste = new int[(const int)(sizee)];

     mflow = new int[(const int)(sizee)];

     spfa();

     spfa();

 }

 inline void solve(){

     cost = ;

     minCostFlow();

     printf("%d\n", cost);

     g.clean();

 }

 int main(){

     while(init()){

         solve();

     }

     return ;

 }