> #include <iostream>
> #include <cstring>
> #include <cstdio>
> #include <cstdlib>
> #include <cmath>
> #include <string>
> #include <vector>
> #include <list>
> #include <map>
> #include <queue>
> #include <stack>
> #include <bitset>
> #include <algorithm>
> #include <numeric>
> #include <functional>
> #include <set>
> #include <fstream>
> 
> using namespace std;
> 
> const int maxn=10010;
> const int INF=0x7fffffff;
> int N,M;
> int a[maxn],b[maxn],c[maxn];
> struct edge {
>     int to,cap,cost,rev;
> };
> int V;
> vector<edge> G[maxn];
> int dist[maxn];
> int prevv[maxn],preve[maxn];
> /*
> void add_edge(int from,int to,int cap,int cost)
> {
>     G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
>     G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
> }
> 
> int min_cost_flow(int s,int t,int f)
> {
>     int res=0;
>     while (f>0) {
>         fill(dist, dist+V, INF);
>         dist[s]=0;
>         bool update=true;
>         while (update) {
>             update=false;
>             for (int v=0; v<V; v++) {
>                 if (dist[v]==INF) {
>                     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) {
>                         dist[e.to]=dist[v]+e.cost;
>                         prevv[e.to]=v;
>                         preve[e.to]=i;
>                         update=true;
>                     }
>                 }
>             }
>         }
>         if (dist[t]==INF) {
>             return -1;
>         }
>         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*dist[t];
>         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;
>         }
>     }
>     return res;
> }
> */
> int h[maxn];
> typedef pair<int, int> P;
> void add_edge(int from,int to,int cap,int cost)
> {
>     G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
>     G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
> }
> 
> int min_cost_flow(int s,int t,int f)
> {
>     int res=0;
>     fill(h, h+V, 0);
>     while (f>0) {
>         priority_queue<P,vector<P>,greater<P> > que;
>         fill(dist, dist+V, INF);
>         dist[s]=0;
>         que.push(P(0,s));
>         while (!que.empty()) {
>             P p=que.top();
>             que.pop();
>             int v=p.second;
>             if (dist[v]<p.first) {
>                 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]==INF) {
>             return -1;
>         }
>         for (int v=0; 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];
>         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;
>         }
>     }
>     return res;
> }
> 
> int main()
> {
>     //freopen("/Users/apple/Desktop/2135/2135/in", "r", stdin);
>     //freopen("/Users/apple/Desktop/2135/2135/out", "w", stdout);
>     while ((scanf("%d%d",&N,&M))!=EOF) {
>         V=N;
>         for (int i=0; i<M; i++) {
>             scanf("%d%d%d",&a[i],&b[i],&c[i]);
>         }
>         int s=0,t=N-1;
>         for (int i=0; i<M; i++) {
>             add_edge(a[i]-1, b[i]-1, 1, c[i]);
>             add_edge(b[i]-1, a[i]-1, 1, c[i]);
>         }
>         int res2=min_cost_flow(s, t, 2);
>         printf("%d\n",res2);
>     }
>     return 0;
> }