#include <iostream>
#include <fstream>
using namespace std;
ifstream f("traseu.in");
ofstream g("traseu.out");

#define mp make_pair
#define x first
#define y second
#define LE 266
#define mp make_pair
#define pii pair<int,int>

int i,n,j,_dr[LE];
int D[LE][LE],que[10*LE];
pii cap[LE][LE];
int father[LE],m,grad[LE];

void roy_floyd()
{
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            for(int k=1; k<=n; ++k)
                if (D[j][i]&&D[i][k]&&(D[j][i]+D[i][k]<D[j][k]||D[j][k]==0))
                    D[j][k]=D[j][i]+D[i][k];
}

#define inf (1<<30)

bool bell_man(int source,int dest)
{
    int i,j,k=0;
    for(i=0; i<=n+n+1; ++i) _dr[i]=inf;
    _dr[source]=0;

    que[++k]=source;

    for(i=1; i<=k; ++i)
        for(j=0; j<=n+n+1; ++j)
            if (cap[que[i]][j].x)
                if (_dr[j]>_dr[que[i]]+cap[i][j].y)
                {
                    _dr[j]=_dr[que[i]]+cap[i][j].y;
                    que[++k]=j;
                    father[j]=que[i];
                }
    if(_dr[dest]==inf) return false;
    return true;
}

int _gflow(int source,int dest)
{
    int result=0;

    while (bell_man(source,dest))
    {
        int nod=dest,fmax=inf,cost=0;

        for (; nod!=source; nod=father[nod])
        {
            fmax=min(fmax,cap[father[nod]][nod].x);
            cost+=cap[father[nod]][nod].y;
        }

        for(nod=dest; nod!=source; nod=father[nod])
        {
            cap[father[nod]][nod].x-=fmax;
            cap[nod][father[nod]].x+=fmax;
        }
        result+=(fmax*cost);
    }

    return result;
}
int suma=0;
int main()
{
    f>>n>>m;
    for(i=1; i<=m; ++i)
    {
        int xx,yy,cc;
        f>>xx>>yy>>cc;
        D[xx][yy]=cc;
        grad[xx]++;
        grad[yy]--;
        suma+=cc;
    }

    roy_floyd();

    //for(i=1;i<=n;++i,cout<<'\n')
     // for(j=1;j<=n;++j)
       // cout<<D[i][j]<<" ";

        //cout<<'\n'<<'\n';

   // for(i=1;i<=n;++i)  cout<<grad[i]<<" ";
   // cout<<'\n';


    for(i=1; i<=n; ++i)
    {
        if(grad[i]<0) cap[0][i]=mp(-grad[i],0);
        if (grad[i]>0) cap[i+n][n+n+1]=mp(grad[i],0);
    }

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j) if (D[i][j])
                if (grad[j]>0&&grad[i]<0) cap[i][n+j]=mp(inf,D[i][j]);



   // for(i=0;i<=n+n+1;++i,cout<<'\n')
   //    for(j=0;j<=n+n+1;++j) cout<<cap[i][j].x<<" ";

    g<<_gflow(0,n+n+1)+suma;



    f.close();
    g.close();
    return 0;
}