#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int INF=2000000000;
int n,m,i,j,x,y,check,cmin[50005],c,modif[50005],nrmodif[50005];
 
vector <pair <int,int> > cacao[50005];

vector <pair <int,int> >::iterator a;

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
 
    scanf("%d%d",&n,&m);
	
	for(i=0;i<=m;++i){
		
		scanf("%d%d%d",&x,&y,&c);
		
		cacao[x].push_back(make_pair(y,c));
		
	}
	
	for(i=0;i<=n;++i){
		cmin[i]=INF;
		
	}
	cmin[1]=0;
	queue <int> Q;
	Q.push(1);
	
	while(!Q.empty() && !check){										//cat timp nu am gasit ciclu si coada nu este vida
		
		x=Q.front();													//scot primul element din coada
		
		Q.pop();
		
		modif[x]=0;														//marchez ca nodul x a fost scos din coada
		
		for(a=cacao[x].begin();a!=cacao[x].end();++a){					//parcurg lista de vecini ai nodului x;
			
			if(cmin[x]<INF){											//daca am gasit drum pana la x (adica daca are rost sa caut drumuri care trec prin x)
				
				if(cmin[a->first] > cmin[x]+a->second){					//daca drumul minim poate fi optimizat
					
					cmin[a->first] = cmin[x]+a->second;					//il optimizez
					
					if(!modif[a->first]){								//daca nodul curent nu se gaseste in coada
						
						if(nrmodif[a->first] > n){						//daca un element a fost modificat de mai mult de n ori
																		//( adica am trecut prin el de mai multe ori decat maximul admis)
							check=1;									//inseamna ca am ciclat intr-un ciclu negativ;
							
						}
						else{											//altfel adaug nodul pe care il prelucrez, marchez ca acesta se gaseste in coada si cresc numarul de aparitii al acestuia in coada;
							
							Q.push(a->first);
							modif[a->first]=1;
							++nrmodif[a->first];
						
						}
						
					}
					
				}
				
			}
			
		}
		
	}
	if(check) printf("Ciclu negativ!");
	else{
		for(i=2;i<=n;++i){
		
			printf("%d ",cmin[i]);
		
		}

		
	}

    return 0;
}