还在因为这一题SPFA被卡而痛不欲生吗？还在因为SPFA的魔法时间复杂度而感到苦恼吗？没关系，我们将使用魔法打败魔法！只需要一个经验值——当出队次数大于 $10^6$ 时，直接判断无解即可通过本题！！！

就像这样：

auto spfa = [&]() -> int {
  V<int> dist(n + 1, -1e18), cnt(n + 1, 0), st(n + 1, 0);
	queue<int> q;
	q.push(0), st[0] = 1, dist[0] = 0;
	int count = 0;
	while (q.size()) {
		int u = q.front();
		q.pop(), st[u] = 0;
		if (++count >= 1e6) return -1; // trick 不然过不去
		for (auto [v, w] : g[u])
			if (dist[v] < dist[u] + w) {
				dist[v] = dist[u] + w, cnt[v] = cnt[u] + 1;
				if (cnt[v] > n) return -1;
				if (!st[v]) q.push(v), st[v] = 1;
			}
	}
	int tot = 0;
	for (int i = 1; i <= n; i++) tot += dist[i];
	return tot;
};