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

#define INF 0x3F3F3F

using namespace std;

bool inq[65];
vector<int> v[65];
int n, m, cost[65][65], cc[65][65], nodin[65], nodout[65], p[65], d[65], source, dest;


int belmanFord()
{
    int nod;
    memset(d, INF, sizeof(d));
    memset(p, 0, sizeof(p));
    memset(inq, 0, sizeof(inq));
    d[source] = 0;
    
    queue<int> q;
    q.push(source);
    while (!q.empty()) {
        nod = q.front();
        q.pop();
        
        for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
        {
            if (d[nod]+cost[nod][*it]<d[*it] && cc[nod][*it]>=1)
            {
                d[*it] = d[nod]+cost[nod][*it];;
                p[*it] = nod;
                if (!inq[*it])
                {
                    q.push(*it);
                    inq[*it] = true;
                }
            }
        }
    }
    return d[dest];
}

int main()
{
    fstream fin("traseu.in", fstream::in);
    fin >> n >> m;
    int x, y, flow, nod;
    long result = 0;
    for (int i = 0; i<m;i++)
    {
        fin >> x >> y;
        fin >> cost[x][y];
        cost[y][x] = cost[x][y];
        v[x].push_back(y);
        v[y].push_back(x);
        result += cost[x][y];
        ++nodout[x];
        ++nodin[y];
    }
    fin.close();
    source = 0;
    dest = n+1;
    for(int i = 1;i<=n;i++)
        if (nodin[i] < nodout[i])
        {
            v[i].push_back(dest);
            v[dest].push_back(i);
            cc[i][dest] = nodout[i] - nodin[i];
        }
        else if (nodin[i] > nodout[i])
        {
            v[i].push_back(source);
            v[source].push_back(i);
            cc[source][i] = nodin[i] - nodout[i];
        }
    int l = belmanFord();
    while (l != INF)
    {
        flow = INF;
        for (nod = dest; nod != source; nod = p[nod])
            if (flow > cc[p[nod]][nod])
                flow = cc[p[nod]][nod];
        for (nod = dest; nod != source; nod = p[nod])
        {
            cc[p[nod]][nod] -= flow;
            cc[nod][p[nod]] += flow;
        }
        result += (flow * d[dest]);
        l = belmanFord();
    }
    fstream fout("traseu.out", fstream::out);
    fout << result;
    fout.close();
    return 0;
}