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

using namespace std;

const int INF = 0x3f3f3f3f;

int N, M;
int D[62][62], val[62];
int C[62][62], F[62][62], T[62];
int minD[62], mincost, result;
bool inQ[62];
queue<int> Q;

bool findFlow()
{
    for (int i = 0; i <= N + 1; ++i)
        minD[i] = INF;
    memset(inQ, 0, sizeof(inQ));
    memset(T, 0, sizeof(T));

    minD[0] = 0;
    Q.push(0);
    inQ[0] = true;

    while (!Q.empty())
    {
        int now = Q.front();
        inQ[now] = false;

        for (int i = 0; i <= N + 1; ++i)
            if (F[now][i] < C[now][i] && minD[now] + D[now][i] < minD[i])
            {
                minD[i] = minD[now] + D[now][i];
                T[i] = now;

                if (!inQ[i])
                {
                    Q.push(i);
                    inQ[i] = true;
                }
            }
        Q.pop();
    }

    if (minD[N + 1] == INF) return false;

    mincost += minD[N + 1];
    for (int now = N + 1; now != 0; now = T[now])
        ++F[T[now]][now], --F[now][T[now]];

    return true;
}

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;
        //D[nod2][nod1] = -cost;
        ++val[nod1];
        --val[nod2];
        result += cost;
    }

    for (int i = 1; i <= N; ++i)
    {
        if (val[i] < 0) C[0][i] = -val[i];
        if (val[i] > 0) C[i][N + 1] = val[i];
    }

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (val[i] < 0 && val[j] > 0)
                C[i][j] = INF;

    while (findFlow());

    fout << result + mincost << '\n';

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