this

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100001;
int n,m;
int head[N];
int vis[N];
int sum[N];
int a[N];
int cnt;
queue<int> q; 
struct node{
	int v,w,next;
}edge[N];
inline void add(int u,int v,int w){
	edge[++cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(v,u,w);
	}
	for(int i=1;i<=n;i++){
		add(0,i,0);
	}
	for(int i=1;i<=n;i++){
		a[i]=0x7f;
	}
	q.push(0);
	vis[0]=1;
	a[0]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v;
			if(a[v]>a[u]+edge[i].w){
				a[v]=a[u]+edge[i].w;
				if(vis[v]==0){
					if(sum[v]>n){
						cout<<"NO"<<endl; 
					} 
					q.push(v);
					vis[v]=1;
					sum[v]=sum[u]+1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	
	
	
	
	
	return 0;
}