// luogu-judger-enable-o2 #include<bits/stdc++.h> #define MAXN 105 usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x*10)+(ch-'0'); ch=getchar(); } return x*f; } structnode{ int to,len; }; vector<node>G[MAXN]; int in[MAXN]; voidAddEdge(int u,int v,int len){ node temp; temp.to=v; temp.len=len; G[u].push_back(temp); } int vis[MAXN],dis[MAXN]; int cnt[MAXN]; int n,m; inlineintSPFA(){ queue<int>Q; for (registerint i=0;i<=n;++i){ if (in[i]==0){ vis[i]=1; dis[i]=0; Q.push(i); } } while (Q.size()){ int u=Q.front(); Q.pop(); vis[u]=false; if (++cnt[u]==n){ returnfalse; } if (!vis[u]){ for (registerint i=0;i<G[u].size();++i){ int v=G[u][i].to; int len=G[u][i].len; if (dis[v]>dis[u]+len){ dis[v]=dis[u]+len; if (!vis[v]){ vis[v]=true; Q.push(v); } } } } } returntrue; } inlinevoidInit(){ for (registerint i=0;i<MAXN;++i){ G[i].clear(); } memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); memset(dis,0x3f,sizeof(dis)); } intmain(){ int w=read(); while (w--){ Init(); n=read(),m=read(); while (m--){ int l=read(),r=read(),len=read(); AddEdge(l-1,r,len); AddEdge(r,l-1,-len); in[r]++; } puts(SPFA()?"true":"false"); } }