# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define db long double
# define scn(x) scanf("%I64d",&x)
# define scan(x) scanf("%d",&x)
# define print(x) printf("%d ",x)
# define prnt(x) printf("%I64d ",x);
# define eol printf("\n")
# define IOS ios_base :: sync_with_stdio(0)
# define pe "Possible"
# define ie "Impossible"
# define halt(...) {fo << (__VA_ARGS__) << '\n';exit(0);}
# define rep1(n) for (int qwerty = 1;qwerty <= n;++qwerty)
# define CF
# ifdef CF
# define DEBUG
# endif // CF
# ifdef DEBUG
# define pp(n) cerr << #n << " = " << n << '\n'
# define ppp(v) for (auto it : v) cerr << it << ' ';cerr << '\n'
# define aprint(x,y,z) for (int i = x;i <= y;++i) cerr << z[i] << ' ';cerr << '\n'
# else
# define pp(n) ;
# define ppp(v) ;
# define aprint(x,y,z);
# endif // DEBUG
# define rep(n) for (int i = 1;i <= n;++i)
const int mod = 1e9 + 7;
int F[1 << 8][1 << 8];
int C[1 << 8][1 << 8];
int D[1 << 8];
int From[1 << 8];
int In[1 << 8];
int Out[1 << 8];
int n,m,start,finish;
pair < int , int > Flow(void)
{
    priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > Q;
    for (int i = 1;i <= n;++i)
        D[i] = 1e9,From[i] = -1;
    D[start] = 0;
    Q.push({0,start});
    while (!Q.empty())
    {
        int node = Q.top().y;
        Q.pop();
        for (int i = 1;i <= n;++i)
            if (F[node][i] > 0 && D[i] > D[node] + C[node][i])
                From[i] = node,D[i] = D[node] + C[node][i],Q.push({D[i],i});
    }
    if (D[finish] == 1e9) return {0,0};
    int flow = 1e9;
    for (int vertex = finish;vertex != start;vertex = From[vertex])
        flow = min(flow,F[From[vertex]][vertex]);
    for (int vertex = finish;vertex != start;vertex = From[vertex])
        F[From[vertex]][vertex] -= flow,F[vertex][From[vertex]] += flow;
    return {flow,flow * D[finish]};
}
int main(void)
{
    # ifdef CF
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);
    # endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    IOS;
    int ans = 0;
    fi>>n>>m;
    while (m --)
    {
        int a,b,c;
        fi>>a>>b>>c;++a;++b;
        ++Out[a];
        ++In[b];
        C[a][b] = c;
        C[b][a] = -c;
        F[a][b] = 1 << 15;
        ans += c;
    }
    for (int i = 2;i <= n+1;++i)
        if (In[i] > Out[i])
            F[1][i] = In[i] - Out[i];
        else
            F[i][n+2] = Out[i] - In[i];
    n += 2;
    start = 1;finish = n;
    pair < int , int > flow;
    while (1)
    {
        flow = Flow();
        if (!flow.x) halt(ans);
        ans += flow.y;
    }
    fo << ans << '\n';
    return 0;
}