WA on #1,3,4,5,6,7,8;

TLE on #9.

#include<bits/stdc++.h>
#define M4 (int)(5e4+3)
using namespace std;
int t,n,m,tot,dis[M4],vis[M4],sum[M4];
int head[M4];
struct edge{int nxt,to,w;}h[M4];
void add(int u,int v,int w){
	h[++tot].to=v;
	h[tot].nxt=head[u];
	h[tot].w=w;
	head[u]=tot;
}
queue<int>Q;
void init(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(sum,0,sizeof(sum));
	while(!Q.empty()) Q.pop();
	dis[1]=0;
	vis[1]=1;
	Q.push(1);
}
void SPFA(){
	init();
	while(!Q.empty()){
		int u=Q.front();
		vis[u]=0;
		Q.pop();
		for(int i=head[u];i;i=h[i].nxt){
			int v=h[i].to,w=h[i].w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				sum[v]=sum[u]+1;
				if(sum[v]>=n){
					puts("YES");
					return;
				}
				if(!vis[v]){
					vis[v]=1;
					Q.push(v);
				}
			}
		}
	}
	puts("NO");
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		while(m--){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
			if(w>=0) add(v,u,w);
		}
		SPFA();
	}
	return 0;
}