#include<cstdio>
#include<queue>
#include<cstring>
const int N = 1e2 + 5;
const int M = 1e3 + 5;
struct edge {
	int next,to,w;
}a[M << 1];
int t,n,m,head[N],a_size = 0,cnt[N],dis[N];
bool vis[N];
inline void add(int u,int v,int w) {
	a[++a_size] = (edge){head[u],v,-w};
	head[u] = a_size;
	a[++a_size] = (edge){head[v],u,w};
	head[v] = a_size;
}
bool SPFA() {
	std::queue<int> q;
	for(int i = 0; i<= n; i++) q.push(i),vis[i] = true;
	while(!q.empty()) {
		int u = q.front();
		if(cnt[u] >= n) return false;
		q.pop(),vis[u] = false;
		for(int i = head[u]; i; i = a[i].next) {
			int v = a[i].to,w = a[i].w;
			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				cnt[v] = cnt[u] + 1;
				if(!vis[v]) q.push(v),vis[v] = true;
			}
		}
	}
	return true; 
}
inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')flag = -1;ch = getchar();}
	while(ch >='0' && ch <='9'){x = (x << 3) + (x << 1) + ch - 48;ch = getchar();}
	return x * flag;
}
int main() {
	t = read();
	while(t--) {
		n = read(),m = read();
		memset (head,0,sizeof(head));
        memset (vis,0,sizeof(vis));
        memset (dis,0,sizeof(dis));
        memset (cnt,0,sizeof(cnt));
		for(int i = 1; i <= m; i++) {
			int u = read(),v = read(),w =read();
			add(u - 1,v,w);
		}
		bool flag = SPFA();
		if(flag) puts("true");
		else puts("false");
	}
	return 0;
}