11pts WA+TLE

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int N = 233;
const int M = 5000;

int w, n, m, cnt;
int head[M], dis[N], vis[N], sum[N];
struct Edge{
	int u, v, w, nx;
}e[M];

void add(int u, int v, int w){
	e[++cnt].u = u;
	e[cnt].v = v;
	e[cnt].w = w;
	e[cnt].nx = head[u];
	head[u] = cnt;
}

bool spfa(int s){
	queue<int> q;
	for(int i = 1; i <= n; ++i){
		dis[i] = INF;
		vis[i] = 0;
		sum[i] = 0;
	}
	dis[s] = 0;
	q.push(s);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = head[u]; i; i = e[i].nx){
			int v = e[i].v;
			if(dis[v] > dis[u] + e[i].w){
				dis[v] = dis[u] + e[i].w;
				if(!vis[v])
					q.push(v);
				++sum[v];
				if(sum[v] >= n + 2)
					return true;	
			}
		}
	}
	return false;
}

int main(){
	scanf("%d", &w);
	for(int i = 1; i <= w; ++i){
		for(int i = 1; i <= cnt; ++i){
			e[i].u = 0;
			e[i].v = 0;
			e[i].nx = 0;
			e[i].w = 0;	
			head[i] = 0;
		}
		cnt = 0;
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= m; ++i){
			int u, v, w;
			scanf("%d %d %d", &u, &v, &w);
			add(u - 1, v, w);
			add(v, u - 1, -w);
		}	
		for(int i = 0; i <= n; ++i)
			add(n + 1, i, 0);
		if(spfa(n + 1)) puts("false");
		else puts("true");
	}
	return 0;	
}