#include <bits/stdc++.h>
using namespace std;
ifstream f("traseu.in");
ofstream g("traseu.out");
int cost[400][400], n, dist[400], realdist[400], dist2[400], r[400][400], s, d, sol, flux=0, inq[400], tata[400], di[409][409];;
vector <int> v[400];
struct elem
{
    int x, dist;
    bool operator < (const elem & other) const
    {
        return dist>other.dist;
    }
};
int in[109], out[109], v1[109], v2[109], l1=0, l2=0;
priority_queue <elem> pq;
bool dijk ()
{
    for (int i=1; i<=n; i++)
        dist[i]=1e9, tata[i]=0;
    dist[s]=dist2[s]=0;
    pq.push({s,0});
    while (!pq.empty())
    {
        elem a=pq.top();
        pq.pop();
        if (a.dist==dist[a.x])
        {
            for (auto y:v[a.x])
            {
                int dif=realdist[a.x]-realdist[y]+cost[a.x][y];
                if (r[a.x][y]>0 && dist[y]>dist[a.x]+dif)
                {
                    dist[y]=dist[a.x]+dif;
                    dist2[y]=dist2[a.x]+cost[a.x][y];
                    tata[y]=a.x;
                    pq.push({y, dist[y]});
                }
            }
        }
    }
    for (int i=1; i<=n; i++)
        realdist[i]=dist2[i];
    return (dist[d]!=1e9);
}
void bellman ()
{
    queue <int> q;
    for (int i=1; i<=n; i++)
        realdist[i]=1e9;
    realdist[s]=0;
    q.push (s);
    inq[s]=1;
    while (!q.empty())
    {
        int nod=q.front();
        q.pop();
        inq[nod]=0;
        for (auto y:v[nod])
        {
            if (r[nod][y]>0 && realdist[y]>realdist[nod]+cost[nod][y])
            {
                realdist[y]=realdist[nod]+cost[nod][y];
                if (!inq[y])
                {
                    q.push(y);
                    inq[y]=1;
                }
            }
        }
    }
}
void fmcm ()
{
    bellman ();
    while (dijk())
    {
        int flow=1e9;
        for (int i=d; i!=s; i=tata[i])
        {
            flow=min (flow, r[tata[i]][i]);
            if (!flow)
                break;
        }
        if (flow!=1e9 && flow)
        {
            int cs=0;
            for (int i=d; i!=s; i=tata[i])
            {
                r[tata[i]][i]-=flow;
                r[i][tata[i]]+=flow;
                cs+=cost[tata[i]][i];
            }
            flux+=flow;
            sol+=cs*flow;
        }

    }
}
signed main ()
{
    int m;
    f >> n >> m;
    while (m--)
    {
        int x, y, z;
        f >> x >> y >> z;
        sol+=z;
        in[y]++;
        out[x]++;
        di[x][y]=z;
    }
    for (int k=1; k<=n; k++)
    {
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++)
            {
                if (di[i][k]!=0 && di[k][j]!=0 && (di[i][k]+di[k][j]<di[i][j] || (di[i][j]==0 && i!=j)))
                    di[i][j]=di[i][k]+di[k][j];
            }
        }
    }
    for (int i=1; i<=n; i++)
    {
        if (in[i]>out[i])
            v1[++l1]=i;
        else if (in[i]<out[i])
            v2[++l2]=i;
    }
    s=n+1, d=n+2;
    for (int i=1; i<=l1; i++)
    {
        v[s].push_back(v1[i]);
        v[v1[i]].push_back(s);
        r[s][v1[i]]=in[v1[i]]-out[v1[i]];
    }
    for (int i=1; i<=l2; i++)
    {
        v[v2[i]].push_back(d);
        v[d].push_back(v2[i]);
        r[v2[i]][d]=out[v2[i]]-in[v2[i]];
    }
    for (int i=1; i<=l1; i++)
    {
        for (int j=1; j<=l2; j++)
        {
            int x=v1[i], y=v2[j], z=di[x][y];
            v[x].push_back(y);
            v[y].push_back(x);
            r[x][y]=1e9;
            cost[x][y]=z;
            cost[y][x]=-z;
        }
    }
    n+=2;
    fmcm();
    g <<sol;
}