rt。

#include <bits/stdc++.h>
#define int long long
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }

const int N = 1e2 + 16, MW = 5e3 + 16; 
struct node {
	int to, w; 
}; 
std::vector <node> G1[N], G2[N]; 
int in1[N], in2[N], n, m; 

bool dp1[N][MW], dp2[N][MW]; 

signed main() {
	
	std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr); 
	
	std::cin >> n >> m;
	int maxlimit1 = 0, maxlimit2 = 0; 
	for (int i = 1; i <= m; ++ i) {
		int u, v, w1, w2; std::cin >> u >> v >> w1 >> w2;
		maxlimit1 += w1, maxlimit2 += w2; 
		G1[u].push_back((node) {v, w1}), ++ in1[v]; 
		G2[u].push_back((node) {v, w2}), ++ in2[v]; 
	}
	
	auto tps1 = [&]() -> void {
//		dp[i][j] --> 第 i 个点，是否能经过长度为 j 的路径到达	
		std::queue <int> q;
		for (int i = 1; i <= n; ++ i) 
			if (!in1[i]) q.push(i), dp1[i][0] = 1; 
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = 0; i < (long long)G1[u].size(); ++ i) { // u --> v
				int v = G1[u][i].to, w = G1[u][i].w;
				for (int j = w; j <= maxlimit1; ++ j) dp1[v][j] |= dp1[u][j - w]; 
				if (-- in1[v] == 0) q.push(v); 
			}
		}
		return void(); 
	}; 
	
	auto tps2 = [&]() -> void {
		std::queue <int> q;
		for (int i = 1; i <= n; ++ i) 
			if (!in2[i]) q.push(i), dp2[i][0] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = 0; i < (long long)G2[u].size(); ++ i) {
				int v = G2[u][i].to, w = G2[u][i].w;
				for (int j = w; j <= maxlimit2; ++ j) dp2[v][j] |= dp2[u][j - w];
				if (-- in2[v] == 0) q.push(v); 
			}
		}
		return void(); 
	};
	
	tps1(), tps2(); 
	
	int mlt = max(maxlimit1, maxlimit2);
	for (int i = 0; i <= mlt; ++ i) 
		if (dp1[n][i] && dp2[n][i]) {
			return std::cout << i << "\n", 0; 
		}
	std::cout << "IMPOSSIBLE\n"; 
	
	
	return 0; 
}