#include <bits/stdc++.h>
//#define int long long
//#define double long double
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define endl '\n' 
using namespace std;
typedef long long ll;
const int N = 1e4+5;
const int M = 1e6+5;
const int INF = 0x7f7f7f7f;

struct node{
	int pre,next,to;
	int value,fee;
}a[M];
int k = 1,h[N];

int n,m,s,t,ans;
int dis[M],pre[N];
bool vis[N];

inline void add(int u,int v,int w,int c){
	a[++k] = {u,h[u],v,w,c};
	h[u] = k;
	a[++k] = {v,h[v],u,0,-c};
	h[v] = k;
}

inline bool spfa(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x7f,sizeof(dis));
	
	queue<int > q;
	q.push(s);
	vis[s] = true;
	dis[s] = 0;
	
	while(!q.empty()){
		int f = q.front();
		q.pop(),vis[f] = false;
		
		for(int i = h[f]; i; i=a[i].next){
			int to = a[i].to;
			
			if(a[i].value > 0 && dis[to] > dis[f]+a[i].fee){
				dis[to] = dis[f] + a[i].fee;
				pre[to] = i;
				if(!vis[to]){
					vis[to] = 1;
					q.push(to);
				}
			}
		}
	}
	return dis[n+1] != dis[n+2];
}

inline void solve(){
	int mi=0,ma=0,c;
	while(spfa()){
		mi = INF;
		for(int i = pre[n+1]; i; i=pre[a[i].pre])
			mi = min(mi,a[i].value);
		for(int i = pre[n+1]; i; i=pre[a[i].pre]){
			a[i].value -= mi;
			a[i^1].value += mi;
		}
		c += dis[n+1] * mi;
		ma += mi;
	}
	ans = (ma == 2 ? mi : -1);
} 

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	
	freopen("app.in","r",stdin);
//	freopen("app.out","w",stdout);
	
	pair<int,int > p;
	
	cin >> n >> m;
	
	add(0,1,2,0);
	add(n,n+1,2,0);
	int u,v,c;
	for(int i = 1; i <= m; i++){
		cin >> u >> v >> c;
		add(u,v,1,c);
		add(v,u,1,c);
	}
	
//	for(int i = 1; i <= n; i++){
//		cout << i << " : ";
//		if(!pre[i]) cout << "null";
//		for(int j = pre[i]; j; j=a[j].next)
//			cout << a[j].to << " ";
//		cout << endl;
//	}
	
	solve();
	cout << ans << endl;
	return 0; 
} 

迷迷糊糊拿板子改的，我也不知道在干啥

http://poj.org/problem?id=2135