#include<cstdio>
#include<climits>
#include<queue>
#include<cstring>

using namespace std;
#define ll long long

const int MAX_V = 1e3 + 1;
typedef pair<int, int> P;
struct edge
{
    int to, cap, cost, rev;
    edge (int t, int ca, int co, int r):
        to(t), cap(ca), cost(co), rev(r){}
};
vector<edge> G[MAX_V];
int h[MAX_V], dist[MAX_V], prevv[MAX_V], preve[MAX_V], V, res, ans;

inline void add_edge(int from, int to, int cap, int cost)
{
    G[from].push_back(edge(to, cap, cost, G[to].size()));
    G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
}

void min_cost_flow(int s, int t, int f)
{
    memset(h, 0, sizeof(h));
    while (f > 0)
    {
        priority_queue<P, vector<P>, greater<P> > que;
        fill(dist, dist + V + 1, INT_MAX);
        dist[s] = 0;
        que.push(P(0, s));
        for (int v, dis; !que.empty(); )
        {
            dis = que.top().first, v = que.top().second;
            que.pop();
            if (dist[v] < dis)
                continue;
            for (int i = 0; i < G[v].size(); ++i)
            {
                edge& e = G[v][i];
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
                {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to],
                    prevv[e.to] = v,
                    preve[e.to] = i;
                    que.push(P(dist[e.to], e.to));
                }
            }
        }
        if (dist[t] == INT_MAX)
            return;
        for (int v = 1; v <= V; ++v)
            h[v] += dist[v];
        int d = f;
        for (int v = t; v != s; v = prevv[v])
            d = min(d, G[prevv[v]][preve[v]].cap);
        f -= d, res += d * h[t], ans += d;
        for (int v = t; v != s; v = prevv[v])
        {
            edge& e = G[prevv[v]][preve[v]];
            e.cap -= d, G[v][e.rev].cap += d;
        }
    }
}

int main()
{
    int m;
    scanf("%d%d", &V, &m);
    for (int a, b, c; m--; )
    {
        scanf("%d%d%d", &a, &b, &c);
        add_edge(a, b, 1, c);
        add_edge(b, a, 1, c);
    }
    min_cost_flow(1, V, 2);
    printf("%d\n", res);
    return 0;
}