#include<stdio.h>
#define Nm 62
#define Inf 1000000000
#define min(a,b) ((a)<(b)?(a):(b))
int G[Nm][Nm],K[Nm][Nm],C[Nm][Nm],F[Nm][Nm],De[Nm],Di[Nm],D[Nm],n;
int X[Nm*Nm],Y[Nm*Nm],Q[Nm*Nm],Dm[Nm],Min[Nm],Pre[Nm],m,ans;

void read()
{
    int i,j;

    freopen("traseu.in","r",stdin);
    scanf("%d%d",&n,&m);

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            K[i][j]=Inf;
            
    for(i=0;i<m;++i)
    {
        scanf("%d%d%d",X+i,Y+i,&j);
        ++De[X[i]]; ++Di[Y[i]];
        K[X[i]][Y[i]]=j; ans+=j;
    }
}

int Bellman_Ford()
{
    int l,r,x,y,i;

    Q[l=r=0]=0; Min[0]=Inf; Dm[0]=0;
    for(i=1;i<=n+1;++i)
        Dm[i]=Inf;

    while(l<=r)
    {
        x=Q[l++];
        for(i=0;i<D[x];++i)
        {
            y=G[x][i];
            if(F[x][y]<C[x][y] && Dm[x]+K[x][y]<Dm[y])
            {
                Dm[y]=Dm[x]+K[x][y];
                Min[y]=min(Min[x],C[x][y]-F[x][y]);
                Pre[y]=x;
                Q[++r]=y;
            }
        }
    }

    return Dm[n+1]!=Inf;
}

void solve()
{
    int i,j,k;

    for(k=1;k<=n;++k)
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                K[i][j]=min(K[i][j],K[i][k]+K[k][j]);
                
    for(i=1;i<=n;++i)
        if(Di[i]>De[i])
            for(j=1;j<=n;++j)
                if(De[j]>Di[j])
                    G[i][D[i]++]=j, G[j][D[j]++]=i,
                    C[i][j]=Inf, K[j][i]=-K[i][j];

    for(i=1;i<=n;++i)
    {
        if(Di[i]>De[i])
            G[0][D[0]++]=i, C[0][i]=Di[i]-De[i];
        if(De[i]>Di[i])
            G[i][D[i]++]=n+1, C[i][n+1]=De[i]-Di[i];
    }

    while(Bellman_Ford())
    {
        ans+=Min[n+1]*Dm[n+1];
        i=n+1;
        while(i)
        {
            F[Pre[i]][i]+=Min[n+1];
            F[i][Pre[i]]-=Min[n+1];
            i=Pre[i];
        }
    }
}

void write()
{
    freopen("traseu.out","w",stdout);
    printf("%d\n",ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}