https://www.luogu.com.cn/record/46481705

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct edge
{
	int to,nxt,val;
}e[600008];
int hd[1008],dis[1008],cnt[1008],ecnt;
bool vis[1008];
void add(int u,int v,int val)
{
	e[++ecnt].to=v;
	e[ecnt].val=val;
	e[ecnt].nxt=hd[u];
	hd[u]=ecnt;
}
bool spfa(int s)
{
	queue<int >q;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(s);
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		vis[u]=0;
		q.pop();
		for(int i=hd[u];i;i=e[i].nxt)
		{
			int v=e[i].to,w=e[i].val;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)return 1;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
 			} 
		}
	}
	return 0;
}
int T;
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		memset(e,0,sizeof(e));
		ecnt=0;
		for(int i=1;i<=m;i++)
		{
			int a,b,c;
			cin>>a>>b>>c;
			add(a,b,c);
			if(c>=0)add(b,a,c);
		}
		if(spfa(1))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
 	return 0;
}