#include<bits/stdc++.h>
using namespace std;
const int N=1100,M=50000;
struct edge{int x,y,f,c,pre;}a[M];int alen,last[N],cur[N];
void ins(int x,int y,int f,int c)
{
    a[++alen]={x,y,f,c,last[x]};last[x]=alen;
    a[++alen]={y,x,0,-c,last[y]};last[y]=alen;
}
int n,m,st,ed,d[N];bool v[N];
bool spfa()
{
    queue<int> q;
    memset(d,0x0f,sizeof(d));d[st]=0;
    memset(v,0,sizeof(v));
    q.push(st);v[st]=1;
    while(!q.empty())
	{
        int x=q.front();q.pop();v[x]=0;
        for(int k=last[x];k;k=a[k].pre)if(a[k].f)
		{
            int y=a[k].y;
            if(d[y]>d[x]+a[k].c)
			{
                d[y]=d[x]+a[k].c;
                if(!v[y])q.push(y),v[y]=1;
            }
        }    
    }
    return d[ed]!=d[0];
}
int ans;
int dinic(int x,int f)
{
    if(x==ed) return ans+=d[ed]*f,f;
    int sx=0;
    v[x]=1;
    for(int k=cur[x];k;k=a[k].pre)if(a[k].f)
	{
        cur[x]=k;
        int y=a[k].y;if(v[y])continue;
        if(d[y]==a[k].c+d[x])
		{
            int sy=dinic(y,min(f-sx,a[k].f));
            a[k].f-=sy,a[k^1].f+=sy;
            sx+=sy;if(sx==f) return f;
        }
    }
    if(sx>0)v[x]=0;
    return sx;
}
   
int main()
{
    scanf("%d%d",&n,&m);
	alen=1;memset(last,sizeof(last));
    for(int i=1;i<=m;i++)
	{
        int x,y,c,f;scanf("%d%d%d",&x,&y,&c);
        ins(x,y,1,c);ins(y,x,1,c);
    }
    st=n+1,ed=n+2;
    ins(st,1,2,0);
    ins(n,ed,2,0);
    ans=0;
    while(spfa())
	{
        memcpy(cur,last,sizeof(cur));
        int t=dinic(st,1<<30);
    }
    printf("%d\n",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1100,M=50000;
struct edge{int x,y,f,c,pre;}a[M];int alen,last[N],cur[N];
void ins(int x,int y,int f,int c)
{
    a[++alen]={x,y,f,c,last[x]};last[x]=alen;
    a[++alen]={y,x,0,-c,last[y]};last[y]=alen;
}
int n,m,st,ed,d[N];bool v[N];
bool spfa()
{
    queue<int> q;
    memset(d,0x0f,sizeof(d));d[st]=0;
    memset(v,0,sizeof(v));
    q.push(st);v[st]=1;
    while(!q.empty())
	{
        int x=q.front();q.pop();v[x]=0;
        for(int k=last[x];k;k=a[k].pre)if(a[k].f)
		{
            int y=a[k].y;
            if(d[y]>d[x]+a[k].c)
			{
                d[y]=d[x]+a[k].c;
                if(!v[y])q.push(y),v[y]=1;
            }
        }    
    }
    return d[ed]!=d[0];
}
int ans;
int dinic(int x,int f)
{
    if(x==ed) return ans+=d[ed]*f,f;
    int sx=0;
    v[x]=1;
    for(int k=cur[x];k;k=a[k].pre)if(a[k].f)
	{
        cur[x]=k;
        int y=a[k].y;if(v[y])continue;
        if(d[y]==a[k].c+d[x])
		{
            int sy=dinic(y,min(f-sx,a[k].f));
            a[k].f-=sy,a[k^1].f+=sy;
            sx+=sy;if(sx==f) return f;
        }
    }
    if(sx>0)v[x]=0;
    return sx;
}
   
int main()
{
    scanf("%d%d",&n,&m);
	alen=1;memset(last,0,sizeof(last));
    for(int i=1;i<=m;i++)
	{
        int x,y,c,f;scanf("%d%d%d",&x,&y,&c);
        ins(x,y,1,c);ins(y,x,1,c);
    }
    st=n+1,ed=n+2;
    ins(st,1,2,0);
    ins(n,ed,2,0);
    ans=0;
    while(spfa())
	{
        memcpy(cur,last,sizeof(cur));
        int t=dinic(st,1<<30);
    }
    printf("%d\n",ans);
    return 0;
}