#include <iostream>#include <cstdio>#include <vector>#include <queue> using namespace std;const long long INF = 0x3f3f3f3f3f3f3f3f;typedef long long ll;typedef pair<ll,int> P;struct edge{    int to,cap;	ll cost;	int rev;	};int V,E;vector<edge> G[1005];ll h[1005];ll dist[1005];int prevv[1005];int preve[1005];void add_edge(int from,int to,int cap,ll cost){	edge e;	e.to = to;	e.cap = cap;	e.cost = cost;	e.rev = G[to].size();	G[from].push_back(e);	e.to = from;	e.cap = 0;	e.cost = -cost;	e.rev = G[from].size() - 1;	G[to].push_back(e);}ll min_cost_flow(int s,int t,int f){	ll 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(){	int a,b;	ll c;    cin >> V >> E;        for(int i = 0;i < E;i ++)    {    	scanf("%d%d%lld",&a,&b,&c);        add_edge(a,b,1,c);        add_edge(b,a,1,c);	}	add_edge(0,1,2,0);	add_edge(V,V + 1,2,0);	V += 2;	cout << min_cost_flow(0,V - 1,2) << endl;    return 0;	}