#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=1;i<=n;++i){
		
		scanf("%d%d%d",&x,&y,&c);
		
		cacao[x].push_back(make_pair(y,c));
		
	}
	
	for(i=1;i<=n;++i){
		cmin[i]=INF;
		
	}
	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)
												//inseamna ca am ciclat intr-un ciclu negativ;
							
							check=1;
							
						}
						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]);
		
		}

		
	}
	//ist[1] = 0, Q.push(1), in_queue[1].flip();
    return 0;
}