spfa #15 #16 #18 #19 #20 TLE

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b, c;
struct egde {
	int x, y, p, q;
} e[200001];
long long dp[200001], tot;
int x, y, p, q;
bool cmp(egde a, egde b) {
	if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}
queue<int> que;
int vis[200001];
long long sum(int i, int j) {
	return a * (e[i].p - e[j].q) * (e[i].p - e[j].q) + b * (e[i].p - e[j].q) + c;
}
int main() {
    ios::sync_with_stdio(false);
	cin >> n >> m >> a >> b >> c;
	for (int i = 1; i <= m; i++)
		cin >> e[i].x >> e[i].y >> e[i].p >> e[i].q;
	for (int i = 0; i <= m; i++) {
		if (e[i].y == n) {
			dp[i] = e[i].q;
			que.push(i);
		} else dp[i] = 0x3f3f3f3f3f3f3f3f;
	}
	while (que.size()) {
		int u = que.front();
		que.pop();
		vis[u] = 0;
		for (int i = 0; i <= m; i++)
			if ((i == 0 && e[u].x == 1) || (e[i].y == e[u].x && e[i].q <= e[u].p)) {
				if (dp[u] + sum(u, i) < dp[i]) {
					dp[i] = dp[u] + sum(u, i);
					if (vis[i] == 0) {
						que.push(i);
						vis[i] = 1;
					}
				}
			}
	}
	cout << dp[0] << endl;
}