#include <fstream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int N, M;
int D[62][62];
int val[62], result;

int main()
{
    ifstream fin("traseu.in");
    ofstream fout("traseu.out");

    fin >> N >> M;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            D[i][j] = INF;
    for (int i = 1; i <= N; ++i)
        D[i][i] = 0;

    for (int i = 1, nod1, nod2, cost; i <= M; ++i)
    {
        fin >> nod1 >> nod2 >> cost;
        D[nod1][nod2] = cost;
        ++val[nod1];
        --val[nod2];
        result += cost;
    }

    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (i != k && j != k && i != j && D[i][k] + D[k][j] < D[i][j])
                    D[i][j] = D[i][k] + D[k][j];

    while (true)
    {
        bool ok = true;
        for (int i = 1; i <= N; ++i)
            if (val[i] != 0)
                ok = false;
        if (ok) break;

        int valn = INF, pos1 = 0, pos2 = 0;
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (val[i] < 0 && val[j] > 0 && D[i][j] < valn)
                {
                    valn = D[i][j];
                    pos1 = i;
                    pos2 = j;
                }

        result += valn;
        ++val[pos1];
        --val[pos2];
    }

    fout << result << '\n';

    fin.close();
    fout.close();
}