用Dijkstra跑90分，#9TLE，求调

#include<bits/stdc++.h>
using namespace std;
void quick(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int read(){
	int x=0;
	bool d=false;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')d=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return d?-x:x;
}
int n,m,tot=0;
const int inf=0x3f3f3f3f;
int head[100010],dis[100010];
int nxt[100010],to[100010],wc[100010];
void add(int a,int b,int w){
	tot++;
	nxt[tot]=head[a];
	head[a]=tot;
	to[tot]=b;
	wc[tot]=w;
}
struct use{
	int id,dis,cnt,fa;
	bool operator <(const use &a)const{
		return dis>a.dis;
	}
};
void abab(){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
	priority_queue<use>q;
	use s;
	s.id=1,s.dis=0,s.cnt=1,s.fa=0;
	q.push(s);
	int i;
	use op,now;
	while(!q.empty()){
		op=q.top();q.pop();
		if(op.dis>=dis[op.id]){
			continue;
		}
		if(op.cnt>n){
			cout<<"YES"<<endl;
			return;
		}
//		cout<<op.id<<' '<<op.cnt<<endl;
		dis[op.id]=op.dis;
		for(i=head[op.id];i!=0;i=nxt[i]){
//			if(to[i]==op.fa)continue;
			if(dis[op.id]+wc[i]<dis[to[i]]){
				now.cnt=op.cnt+1;
				if(now.cnt>n){
					cout<<"YES"<<endl;
					return;
				}
				now.id=to[i];
				now.dis=dis[op.id]+wc[i];
				now.fa=op.id;
				q.push(now);
			}
		}
	}
	cout<<"NO"<<endl;
	return;
}
int main(){
//	freopen("P3385_1.in","r",stdin);
//	quick();
	int t;
//	cin>>t;
	t=read();
	while(t--){
		memset(head,0,sizeof(head));
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			int a,b,w;
//			cin>>a>>b>>w;
			a=read(),b=read(),w=read();
			if(w<0)add(a,b,w);
			else{
				add(a,b,w);
				add(b,a,w);
			}
		}
		abab();
	}
	return 0;
}