#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 1010;
int dis[N], pre[N], preve[N];
int n, m;
struct edge
{
    int to, cost, capacity, rev;
    edge(int to_, int cost_, int c, int rev_)
    {
        to = to_;
        cost = cost_;
        capacity = c;
        rev = rev_;
    }
};
vector<edge> e[N];
void addedge(int from, int to, int cost, int capacity)
{
    e[from].push_back(edge(to, cost, capacity, e[to].size()));
    e[to].push_back(edge(from, -cost, 0, e[from].size() - 1));
}
bool spfa(int s, int t, int cnt)
{
    bool inq[N];
    memset(pre, -1, sizeof(pre));
    for (int i = 1; i <= cnt; i++)
    {
        dis[i] = INF;
        inq[i] = false;
    }
    dis[s] = 0;
    queue<int> Q;
    Q.push(s);
    inq[s] = true;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        inq[u] = false;
        for (int i = 0; i < e[u].size(); i++)
            if (e[u][i].capacity > 0)
            {
                int v = e[u][i].to, cost = e[u][i].cost;
                if (dis[u] + cost < dis[v])
                {
                    dis[v] = dis[u] + cost;
                    pre[v] = u;
                    preve[v] = i;
                    if (!inq[v])
                    {
                        inq[v] = true;
                        Q.push(v);
                    }
                }
            }
    }
    return dis[t] != INF;
}
int mincost(int s, int t, int cnt)
{
    int cost = 0;
    while (spfa(s, t, cnt))
    {
        int v = t, flow = INF;
        while (pre[v] != -1)
        {
            int u = pre[v], i = preve[v];
            flow = min(flow, e[u][i].capacity);
            v = u;
        }
        v = t;
        while (pre[v] != -1)
        {
            int u = pre[v], i = preve[v];
            e[u][i].capacity -= flow;
            e[v][e[u][i].rev].capacity += flow;
            v = u;
        }
        cost += dis[t] * flow;
    }
    return cost;
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 0; i < N; i++)
            e[i].clear();
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w, 1);
            addedge(v, u, w, 1);
        }
        int s = n + 1, t = n + 2;
        addedge(s, 1, 0, 2);
        addedge(n, t, 0, 2);
        printf("%d\n", mincost(s, t, n + 2));
    }
    return 0;
}