#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#define inf (2e8)
using namespace std;
int n,m;
struct node
{
    int next,to,cap,cost;
}edge[50001];
int head[1001],size=1;
void putin(int from,int to,int cap,int cost)
{
    size++;
    edge[size].next=head[from];
    edge[size].to=to;
    edge[size].cap=cap;
    edge[size].cost=cost;
    head[from]=size;
}
void in(int from,int to,int cap,int cost)
{
    putin(from,to,cap,cost);
    putin(to,from,0,-cost);
}
int dist[1005],vis[1005],pre[1005],ans;
bool bfs(int src,int des)
{
    queue<int>mem;
    int i,j;
    for(i=0;i<=n;i++){dist[i]=inf;vis[i]=0;}
    mem.push(src);dist[0]=0;
    while(!mem.empty())
    {
        int x=mem.front();mem.pop();
        for(i=head[x];i!=-1;i=edge[i].next)
        {
            int y=edge[i].to;
            if(dist[y]>dist[x]+edge[i].cost&&edge[i].cap>0)
            {
                dist[y]=dist[x]+edge[i].cost;
                pre[y]=i;
                if(!vis[y]){mem.push(y);vis[y]=1;}
            }
        }
        vis[x]=0;
    }
    if(dist[des]==inf)return false;
    else
    {
        ans=ans+dist[des];
        return true;
    }
}
void change(int src,int des)
{
    int x=des;
    while(x!=src)
    {
        edge[pre[x]].cap--;
        edge[pre[x]^1].cap++;
        x=edge[pre[x]^1].to;
    }
}
int min_cost_flow(int src,int des)
{
    ans=0;
    while(bfs(src,des))change(src,des); 
    return ans;
}
int main()
{
    int i,j;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    in(0,1,2,0);
    for(i=1;i<=m;i++)
    {
        int from,to,cost;
        scanf("%d%d%d",&from,&to,&cost);
        in(from,to,1,cost);
        in(to,from,1,cost);
    }
    cout<<min_cost_flow(0,n);
    return 0;
}