#include <iostream>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <map>

 #include <set>

 #include <string>

 #include <queue>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, a, n) for(int i = a; i<n; i++)

 #define ull unsigned long long

 typedef pair<int, int> pll;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int dir[][] = { {, }, {, }, {, -}, {, } };

 const int maxn = 4e5+;

 int num, head[maxn*], s, t, n, m, nn, dis[maxn], flow, cost, cnt, cap[maxn], q[maxn], cur[maxn], vis[maxn];

 struct node

 {

     int to, nextt, c, w;

     node(){}

     node(int to, int nextt, int c, int w):to(to), nextt(nextt), c(c), w(w) {}

 }e[maxn*];

 int spfa() {

     int st, ed;

     st = ed = ;

     mem2(dis);

     ++cnt;

     dis[s] = ;

     cap[s] = inf;

     cur[s] = -;

     q[ed++] = s;

     while(st<ed) {

         int u = q[st++];

         vis[u] = cnt-;

         for(int i = head[u]; ~i; i = e[i].nextt) {

             int v = e[i].to, c = e[i].c, w = e[i].w;

             if(c && dis[v]>dis[u]+w) {

                 dis[v] = dis[u]+w;

                 cap[v] = min(c, cap[u]);

                 cur[v] = i;

                 if(vis[v] != cnt) {

                     vis[v] = cnt;

                     q[ed++] = v;

                 }

             }

         }

     }

     if(dis[t] == inf)

         return ;

     cost += dis[t]*cap[t];

     flow += cap[t];

     for(int i = cur[t]; ~i; i = cur[e[i^].to]) {

         e[i].c -= cap[t];

         e[i^].c += cap[t];

     }

     return ;

 }

 int mcmf() {

     flow = cost = ;

     while(spfa())

         ;

     return cost;

 }

 void add(int u, int v, int c, int val) {

     e[num] = node(v, head[u], c, val); head[u] = num++;

     e[num] = node(u, head[v], , -val); head[v] = num++;

 }

 void init() {

     mem1(head);

     num = cnt = ;

     mem(vis);

 }

 void input() {

     int x, y, w;

     while(m--) {

         scanf("%d%d%d", &x, &y, &w);

         add(x, y, , w);

         add(y, x, , w);

     }

     add(s, , , );

     add(n, t, , );

 }

 int main()

 {

     while(~scanf("%d%d", &n, &m)) {

         init();

         s = , t = n+;

         input();

         int ans = mcmf();

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

     }

     return ;

 }