处女座的比赛资格
思路：
负权跑不能用迪杰斯特拉
跑 $spfa$ 会被卡
细心的可以发现这是一张有向无环图，因此可以拓扑排序求单源最短路
坑点：
如果最短路是负的，说明走到终点不仅没有花费，还赚了，这时候应该置为 $0$
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 1e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
ll dis[maxn];
struct node{
	int next, to, w;
}e[maxn << 2];
int head[2][maxn], cnt, in[maxn], deg[maxn];

void add(int op, int x, int y, int z){
	e[++cnt].to = y;
	e[cnt].w = z;
	e[cnt].next = head[op][x];
	head[op][x] = cnt;
}
ll topsort(int op){
	for(int i = 1; i <= n; ++i) deg[i] = in[i];
	queue <int> q;mem(dis, 0x3f);dis[1] = 0;
	for(int i = 1; i <= n; ++i) if(!in[i]) q.push(i);
	while(!q.empty()){
		int x = q.front();q.pop();
		for(int i = head[op][x]; i; i = e[i].next){
			int to = e[i].to;
			deg[to]--;
			if(!deg[to]) q.push(to);
			dis[to] = min(dis[to], dis[x] + 1ll * e[i].w);
		}
	}
	return max(0ll, dis[n]);
}
void work()
{
	mem(head, 0);cnt = 0;mem(in, 0);
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int x, y, z, a, b;cin >> x >> y >> z >> a >> b;
		add(0, x, y, z - a);add(1, x, y, z - b);in[y]++;
	}
	ll ans1 = topsort(0);
	ll ans2 = topsort(1);
	if(ans1 < ans2) cout << "cnznb!!!\n" << ans2 - ans1 << endl;
	else if(ans1 > ans2) cout << "rip!!!\n" << ans1 - ans2 << endl;
	else cout << "oof!!!\n"; 
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}