spfa TLE#9求助

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue> 
using namespace std;
const int N=2e4+5,M=3e4+5;
int h[N],to[M],ne[M],w[M],d[N],cnt[N],idx=1,n,m,tot;
bool vst[N]={false};

void add(int u,int v,int c)
{
	to[idx]=v;
	w[idx]=c;
	ne[idx]=h[u];
	h[u]=idx++;
}

bool spfa()
{
	queue<int> q;
	d[1]=0;
	vst[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vst[t]=0;
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int v=to[i];
			if(d[v]>d[t]+w[i])
			{
				d[v]=d[t]+w[i];
				if(!vst[v])
				{
					vst[v]=1;
					q.push(v);
					cnt[v]++;
					if(cnt[v]>=n) return true;
				}
			}
		}
	}
	return false;
}
 
int main()
{
	cin>>tot;
	while(tot--)
	{
		cin>>n>>m;
		memset(h,-1,sizeof(h));
		memset(d,0x3f,sizeof(d));
		memset(cnt,0,sizeof(cnt));
		memset(vst,false,sizeof(vst));
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			add(u,v,w);
			if(w>=0) add(v,u,w);
		}
		spfa()?(cout<<"YES\n"):(cout<<"NO\n");
	}
	return 0;	
}