{
	int@n,@m;
	minCostFlow<ll,ll> g;
	g.malloc(n);
	g.init(n);
	rep(m){
		int@u,@v;ll@c,@d;u--;v--;
		g.addEdge(u,v,1,c);
		g.addEdge(v,u,1,c);
		g.addEdge(u,v,1,d);
		g.addEdge(v,u,1,d);
	}
	ll f,c;
	g.solve(0,n-1,f,c,2);
	wt(c);
}