WA 37pts求调,玄关

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
struct node{
	int v,w;
};
int n,m,d[50000],cnt[50000];
bool in[50000];
vector<node> g[50000];
queue<int>q;
bool SPFA(){
	memset(d,0x7f,sizeof(d));
	d[0]=0;
	in[0]=true;
	q.push(0);
	cnt[0]++;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		in[u]=false;
		for(auto i:g[u]){
			int v=i.v,w=i.w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!in[v]){
					cnt[v]++;
					in[v]=true;
					q.push(v);
					if(cnt[v]==n)return false;
				}
			}
		}
	}
	return true;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		g[u].push_back((node){v,-w});
		g[v].push_back((node){u,w});
	}
	for(int i=1;i<=n;i++)g[0].push_back((node){i,0});
	if(SPFA())for(int i=1;i<=n;i++)cout<<d[i]<<' ';
	else cout<<"NO";
}