//Traseu
#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], 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;
 
    result += 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 (D[i][j] > 0)
                C[i][j] = INF;
 
    while (findFlow());
 
    fout << result << '\n';
 
    fin.close();
    fout.close();
}