#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
ifstream cin("traseu.in");
ofstream cout("traseu.out");

using pi = pair<int,int>;
const int N = 69, Inf = 0x3f3f3f3f;
int n,m,a,b,c;
int in[N],out[N],d[N],t[N];
int dist[N][N],C[N][N];
vector<vector<pi>> G;
vector<vector<pi>> Graf;

void RF()
{
    memset(dist,Inf,sizeof(dist));
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(i != j && dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}
void BuildGraf()
{
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i != j && dist[i][j] != Inf)
            {
                Graf[i].push_back({j,dist[i][j]});
                C[i][j] = Inf;
            }

    for(int i = 1; i <= n; ++i)
        if(in[i] > out[i])
        {
            Graf[0].push_back({i,0});
            C[0][i] = in[i] - out[i];
        }

    for(int i = 1; i <= n; ++i)
        if(in[i] < out[i])
        {
            Graf[i].push_back({n+1,0});
            C[i][n+1] = out[i] - in[i];
        }
}

bool Dij(int source,int sink)
{
    priority_queue<pi,vector<pi>,greater<pi>>q;
    memset(d,Inf,sizeof(d));
    d[source] = 0;
    q.push({0,source});

    while(!q.empty())
    {
        int dx  = q.top().first,
        x = q.top().second;

        if(dx > d[x])continue;

        for(auto i : Graf[x])
        {
            int y = i.first,
            w = i.second;

            if(d[y] > d[x] + w)
            {
                d[y] = d[x] + w;
                t[y] = x;
                q.push({d[y],y});
            }
        }
    }

    return (d[sink] != Inf);
}


int MaxFlow(int source,int sink)
{
    int maxflow = 0,fmin;
    while(Dij(source,sink))
    {
        for(int i = sink; i != source; i = t[i])
            fmin = min(fmin,C[t[i]][i]);

        if(fmin)continue;

        for(int i = sink; i != source; i = t[i])
        {
            C[t[i]][i] -= fmin;
            C[i][t[i]] += fmin;
        }

        maxflow += fmin * d[sink];
    }
    return maxflow;
}

int main()
{
    cin>>n>>m;
    G = vector<vector<pi>>(n+1);
    Graf = vector<vector<pi>>(n+3);
    while(m--)
    {
        cin>>a>>b>>c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
        in[b]++;
        out[a]++;
    }


    RF();
    BuildGraf();
    //cout<<MaxFlow(0,n+1);
    return 0;
}