#include<stdio.h>

 #include<algorithm>

 #include<string.h>

 #include<queue>

 #include<math.h>

 using namespace std;

 #define inf   100000000

 #define MAXN 50000

 #define MAXN1 1500

 struct node

 {

     int fr,to,next,fl,w;

 }x[MAXN];

 int cnt,S,T;

 int head[MAXN1],dis[MAXN1],pre[MAXN1];

 bool vis[MAXN1];

 void add(int u,int v,int fl,int w)

 {

     x[cnt].fr=u;

     x[cnt].next=head[u];

     x[cnt].to=v;

     x[cnt].fl=fl;

     x[cnt].w=w;

     head[u]=cnt++;

 }

 queue<int>q1;

 int spfa()  //最短路的话就是可以增广 费用最少

 {

     memset(vis,,sizeof(vis));

     memset(pre,-,sizeof(pre));

     int i;

     for(i=;i<=T;i++)

         dis[i]=inf;

     dis[S]=;

     vis[S]=;

     q1.push(S);

     while(!q1.empty())

     {

         int now=q1.front();

         q1.pop();

         vis[now]=;

         for(i=head[now];i!=-;i=x[i].next)

         {

             if(dis[now]+x[i].w<dis[x[i].to]&&x[i].fl)

             {

                 dis[x[i].to]=dis[now]+x[i].w;

                 pre[x[i].to]=i;

                 if(vis[x[i].to]==)

                 {

                     q1.push(x[i].to);

                     vis[x[i].to]=;

                 }

             }

         }

     }

     int a=pre[T];

     while(a!=-)  //要结束了也可以更新流量

     {

         x[a].fl-=;

         x[a^].fl+=;

         a=pre[x[a].fr];

     }

     return pre[T]!=-;

 }

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         int i;

         cnt=;

         memset(head,-,sizeof(head));

         S=,T=n+;

         for(i=;i<=m;i++)

         {

             int a,b,w;

             scanf("%d%d%d",&a,&b,&w);

             add(a,b,,w),add(b,a,,-w);   //-w  如果有一条更优的路 可以走回来+（-w）;

             add(b,a,,w),add(a,b,,-w);

         }

         add(S,,,),add(,S,,);  //其实就是2次 1->n

         add(n,T,,),add(T,n,,);

         int ans=;

         while(spfa())

             ans=ans+dis[T];

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

     }

     return ;

 }