//HighFlow
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <queue>
#include <fstream>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=(st);i<=(dr);i+=(k))
#define ll (long long)
#define kfl(i,j) (cap[(i)][(j)]-fl[(i)][(j)])
#define nm 65
#define y first
#define INF 2000100
#define cst second
using namespace std;
FILE *f,*g;
int gr_in[nm],gr_out[nm];
int d[nm],tt[nm];
bool in_q[nm];
int cap[nm][nm],fl[nm][nm];
int ans,n,m;
int r[nm][nm];
vector <pair<int,int> > a[nm];


inline void fa_muchie(int x,int y,int capacitate, int cost)
{
    a[x].push_back(make_pair(y,cost));
    cap[x][y]=capacitate;
    a[y].push_back(make_pair(x,-cost));
    cap[y][x]=0;
}


void read()
{
    int i,x,y,c,k,j;
    f=fopen("traseu.in","r");
    g=fopen("traseu.out","w");

    fscanf(f,"%d%d",&n,&m);

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) r[i][j]=INF;

    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        gr_out[x]++;
        gr_in[y]++;
        ans+=c;
        r[x][y]=c;
    }

    for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                r[i][j]=min(r[i][j],r[i][k]+r[k][j]);

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if ( i!=j  && gr_in[i]>gr_out[i] && gr_in[j]<gr_out[j] )
                fa_muchie(i,j,INF,r[i][j]);

    for (i=1;i<=n;i++)
        if (gr_in[i]>gr_out[i])
            fa_muchie(0,i,gr_in[i]-gr_out[i],0);
        else
            if (gr_in[i]<gr_out[i])
                fa_muchie(i,n+1,gr_out[i]-gr_in[i],0);
}

inline bool bellman()
{
    int i,j,x,mn;
    queue <int> q;

    for (i=1;i<=n+1;i++) d[i]=INF,tt[i]=-1,in_q[i]=false;
    d[0]=0; in_q[0]=true;
    q.push(0);

    while (q.size())
    {
        x=q.back();
        q.pop();
        in_q[x]=false;

        for (i=0;i<a[x].size();i++)
            if (cap[x][a[x][i].y]-fl[x][a[x][i].y]>0 && d[a[x][i].y]>d[x]+a[x][i].cst)
            {
                d[a[x][i].y]=d[x]+a[x][i].cst;
                tt[a[x][i].y]=x;
                if (in_q[a[x][i].y]==false)
                {
                    in_q[a[x][i].y]=true;
                    q.push(a[x][i].y);
                }
            }
    }


    if (tt[n+1]==-1) return false;

    for (mn=INF,i=n+1;i!=0;i=tt[i]) mn=min(mn,kfl(tt[i],i));
    for (i=n+1;i!=0;i=tt[i])
    {
        fl[tt[i]][i]+=mn;
        fl[i][tt[i]]-=mn;
    }
    ans=ans+d[n+1]*mn;
    return true;
}


void solve()
{
    while (bellman()) ;
    fprintf(g,"%d",ans);
}

int main()
{
    read();
    solve();

	return 0;
}