记录编号	358897	评测结果	AAAAAAAAAAAAAAA
题目名称	相遇时间	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2016-12-19 16:38:41	内存使用	0.31 MiB

//KZNS
#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define Nmax 103
typedef pair<int, int> poi;
class pr {
public:
	int t, v;
	bool operator () (const pr a, const pr b) {
		return a.v > b.v;
	}
};

int N, M;
class PE {
public:
	vector<poi> gp[Nmax];
	priority_queue<pr, vector<pr>, pr> ls;
	void fir() {
		ls.push((pr){1, 0});
	}
	int stt() {
		int ans = -1;
		pr pru;
		int x, v;
		while (!ls.empty()) {
			pru = ls.top();
			ls.pop();
			x = pru.t;
			v = pru.v;
			if (x == N) {
				ans = v;
				break;
			}
			for (int i = 0; i < gp[x].size(); i++)
				ls.push((pr){gp[x][i].first, v+gp[x][i].second});
		}
		return ans;
	}
} AA, BB;
void init() {
	scanf("%d %d", &N, &M);
	int a, b, c, d; 
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		AA.gp[a].push_back(make_pair(b, c));
		BB.gp[a].push_back(make_pair(b, d));
	}
	AA.fir();
	BB.fir();
}
int main() {
	freopen("meeting.in", "r", stdin);
	freopen("meeting.out", "w", stdout);
	init();
	int a, b;
	a = AA.stt();
	b = BB.stt();
	while (a != b) {
		if (a < b) {
			a = AA.stt();
			if (a == -1)
				b == -1;
		}
		else {
			b = BB.stt();
			if (b == -1)
				a == -1;
		}
	}
	if (a >= 0)
		printf("%d\n", a);
	else
		printf("IMPOSSIBLE\n");
	return 0;
}
//UBWH