#include <fstream>
#include <vector>
#include <queue>
using namespace std;
 
const int N=65,inf=1<<30;
int drum[N][N],cap[N][N],flux[N][N],cost[N][N],grad[N],T[N],dist[N],n;
vector<int> a[N];
queue<int> Q;
 
ifstream in("traseu.in");
ofstream out("traseu.out");
 
inline int min(int a,int b)
{
    return a<b ? a : b;
}
 
inline int dif(int x,int y)
{
    return cap[x][y]-flux[x][y];
}
 
bool bf(int x,int D)
{
    for (int i=1;i<=n+1;i++)
        dist[i]=inf;
    while (!Q.empty())
        Q.pop();
    dist[x]=0;
    Q.push(x);
    while (!Q.empty())
    {
        x=Q.front();Q.pop();
        if (x==D)
            continue;
        for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
            if (dif(x,*i)>0 && dist[x]+cost[x][*i]<dist[*i])
            {
                dist[*i]=dist[x]+cost[x][*i];
                T[*i]=x;
                Q.push(*i);
            }
    }
    return dist[D]!=inf;
}
 
int flow(int S,int D)
{
    int C=0,M;
    while (bf(S,D))
    {
        M=inf;
        for (int i=D;i!=S;i=T[i])
            M=min(M,dif(T[i],i));
        if (!M)
            break;
        for (int i=D;i!=S;i=T[i])
        {
            flux[T[i]][i]+=M;
            flux[i][T[i]]-=M;
        }
        C+=M*dist[D];
    }
    return C;
}
 
inline int scor (int x,int y,int z)
{
    return (x && y && (!z || x+y<z)) ? x+y : z;
}
 
void roy()
{
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (i!=j)
                    drum[i][j]=scor(drum[i][k],drum[k][j],drum[i][j]);
}
 
int main()
{
    int m,x,y,c,C=0;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y>>c;
        drum[x][y]=c;
        C+=c;
        grad[x]++;
        grad[y]--;
    }
    roy();
    for (int i=1;i<=n;i++)
    {
        if (!grad[i])
            continue;
        if (grad[i]<0)
        {
            cap[0][i]=-grad[i];
            a[0].push_back(i);
            a[i].push_back(0);
            for (int j=1;j<=n;j++)
                if (grad[j]>0)
                {
                    cap[i][j]=inf;
                    cost[i][j]=drum[i][j];
                    cost[j][i]=-drum[i][j];
                    a[i].push_back(j);
                    a[j].push_back(i);
                }
            continue;
        }
        cap[i][n+1]=grad[i];
        a[n+1].push_back(i);
        a[i].push_back(n+1);
    }
    out<<C+flow(0,n+1)<<"\n";
    return 0;
}