数据有点水...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k=1,dist[1000005],s,cnt[1000005];
bool tmp[1000005];
struct node{
	ll v;
	ll w;
};
vector<node> a[1000005];
void SPFA(ll s){
	queue<ll> q;
	q.push(s);
	tmp[s]=1;
	cnt[s]=1;
	for(int i=0;i<=n;i++){
		dist[i]=2147483647;
	}
	dist[s]=0;
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		tmp[u]=0;
		for(auto it:a[u]){
			ll v=it.v,w=it.w;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				if(tmp[v]==0){
					tmp[v]=1;
					q.push(v);
					cnt[v]+=1;
					if(cnt[v]>=n){
						cout<<"NO";
						exit(0);
						return ;
					}
				}
			}
		}
	}
	return ; 
}

int main(){

	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		a[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++){ //把n改成m也能过
		a[0].push_back({i,0});
	}
	SPFA(0);
	for(int i=1;i<=n;i++){
		cout<<dist[i]<<" ";
	} 

	return 0;
}