queue;```cpp #include<bits/stdc++.h> using namespace std; int T; int m,n; struct edge{ int v; int w; int next; }Edge[6005]; struct point{ int lo; int dis; int head; bool VIS; }p[2005]; int cnt; void add(){ int u,v,w; cin>>u>>v>>w; Edge[++cnt].v=v; Edge[cnt].w=w; Edge[cnt].next=p[u].head; p[u].head=cnt; if(w>=0){ Edge[++cnt].v=u; Edge[cnt].w=w; Edge[cnt].next=p[v].head; p[v].head=cnt; } return; } bool spfa(){ // priority_ queue<pair<int,int> > q; p[1].VIS=1; q.push(make_pair(0,1)); while(!q.empty()){ int x=q.front().second; // if(p[x].lo>=n) return 1; q.pop(); p[x].VIS=0; int e=p[x].head; while(e){ int y=Edge[e].v,z=Edge[e].w; if(p[y].dis>p[x].dis+z||(!p[y].lo)){ p[y].dis=p[x].dis+z; p[y].lo=p[x].lo+1; // if(p[y].lo>=n) return 1; if(!p[y].VIS){ q.push(make_pair(p[y].lo,y)); p[y].VIS=1; } } if(p[y].lo>=n) return 1; e=Edge[e].next; } } return 0; } int main(){ // std::ios::sync_with_stdio(0); cin>>T; while(T--){ cin>>n>>m; memset(Edge,0,sizeof(struct edge)*6005); memset(p,0,sizeof(struct point)*2005); cnt=0; while(m--){ add(); } if(spfa()) cout<<"YES\n"; else cout<<"NO\n";

}
return 0;

}

priority_queue:

#include<bits/stdc++.h>
using namespace std;
int T;
int m,n;
struct edge{
	int v;
	int w;
	int next;
}Edge[6005]; 
struct point{
	int lo;
	int dis;
	int head;
	bool VIS;
}p[2005];
int cnt;
void add(){
	int u,v,w;
	cin>>u>>v>>w;
	Edge[++cnt].v=v;
	Edge[cnt].w=w;
	Edge[cnt].next=p[u].head;
	p[u].head=cnt;
	if(w>=0){
		Edge[++cnt].v=u;
		Edge[cnt].w=w;
		Edge[cnt].next=p[v].head;
		p[v].head=cnt;
	}
	return;
}
bool spfa(){
	priority_queue<pair<int,int> > q;
	p[1].VIS=1;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int x=q.top().second;
//		if(p[x].lo>=n) return 1;
		q.pop();
		p[x].VIS=0;
		int e=p[x].head;
		while(e){
			int y=Edge[e].v,z=Edge[e].w;
			if(p[y].dis>p[x].dis+z||(!p[y].lo)){
				p[y].dis=p[x].dis+z;
				p[y].lo=p[x].lo+1;
//				if(p[y].lo>=n) return 1;
				if(!p[y].VIS){
					q.push(make_pair(p[y].lo,y));
					p[y].VIS=1;
				}
			}
			if(p[y].lo>=n) return 1;
			e=Edge[e].next;
		}
	}
	return 0;
}
int main(){
	std::ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		memset(Edge,0,sizeof(struct edge)*6005);
		memset(p,0,sizeof(struct point)*2005);
		cnt=0;
		while(m--){
			add();
		}
		if(spfa()) cout<<"YES\n";
		else cout<<"NO\n"; 
		
	}
	return 0;
}