记录编号	203741	评测结果	AAAAA
题目名称	平凡的皮卡丘	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2015-11-03 16:03:47	内存使用	1.38 MiB

#include <algorithm>
#include <cstdio>
#include <queue>
const int kN = 4e4+10;
const int INF = 1e9;
using namespace std;
struct Info {
	int mi1, mi1_from;
	int mi2, mi2_from;
	Info() {
		mi1 = mi2 = INF;
		mi1_from = mi2_from = 0;
	}
};

Info d[kN];
int N, M;
vector<pair<int, int> > G[kN];

bool update(int u, int cost, int from) {
	bool upd = false;
	if (from == d[u].mi1_from || d[u].mi1_from == 0) {
		if (cost < d[u].mi1) {
			d[u].mi1 = cost;
			d[u].mi1_from = from;
			upd = true;
		}
	} else if (from == d[u].mi2_from || d[u].mi2_from == 0) {
		if (cost < d[u].mi2) {
			d[u].mi2 = cost;
			d[u].mi2_from = from;
			upd = true;
		}
	} else {
		if (cost < d[u].mi1) {
			d[u].mi1 = cost;
			d[u].mi1_from = from;
			upd = true;
		} else if (cost < d[u].mi2) {
			d[u].mi2 = cost;
			d[u].mi2_from = from;
			upd = true;
		}
	}
	
	if (d[u].mi1 > d[u].mi2) {
		swap(d[u].mi1, d[u].mi2);
		swap(d[u].mi1_from, d[u].mi2_from);
	}
	
	return upd;
}

int main() {
	// freopen("in.txt", "r", stdin);
	freopen("both.in", "r", stdin);
	freopen("both.out", "w", stdout);
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		int u, v, c1, c2;
		scanf("%d %d %d %d", &u, &v, &c1, &c2);
		G[u].push_back(make_pair(v, c1));
		G[v].push_back(make_pair(u, c2));
	}
	
	queue<int> q;
	for (int i = 0; i < G[1].size(); i++) {
		int v = G[1][i].first, c = G[1][i].second;
		d[v].mi1 = c;
		d[v].mi1_from = v;
		q.push(v);
	}

	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].first, c = G[u][i].second;
			if (v == 1) continue;

			bool upd = false;
			upd |= update(v, d[u].mi1+c, d[u].mi1_from);
			upd |= update(v, d[u].mi2+c, d[u].mi2_from);
			if (upd) {
				q.push(v);
			}
		}
	}
	
	int ans = INF;
	for (int u = 1; u <= N; u++) {
		int tmp = INF;
		for (int i = 0; i < G[u].size(); i++) {
			if (G[u][i].first == 1) {
				tmp = min(tmp, G[u][i].second);
			}
		}
		if (d[u].mi1_from != u) {
			tmp += d[u].mi1;
		} else if (d[u].mi2_from != u) {
			tmp += d[u].mi2;
		}
		
		ans = min(ans, tmp);
	}
	
	if (ans >= INF) ans = -1;
	printf("%d\n", ans);	
	return 0;
}