#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define nmax 50002
using namespace std;
vector <int> lista[nmax],cost[nmax];
queue <int> coada;
int n,m,viz[nmax],dist[nmax];

void citire(){
	scanf("%d%d",&n,&m);
	int x,y,c;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&c);
		lista[x].push_back(y);
		cost[x].push_back(c);
	}
}

void bellman(){
	coada.push(1);
	int nod,costnod;
	memset(dist,100,sizeof(dist));
	dist[1]=0;
	while(coada.size()){
		nod=coada.front();
		costnod=dist[nod];
		coada.pop();
		viz[nod]++;
		if(viz[nod]>n){
			printf("Ciclu negativ!\n");
			return;
		}
		for(unsigned int i=0;i<lista[nod].size();i++)
			if(costnod+cost[nod][i]<dist[lista[nod][i]]){
				dist[lista[nod][i]]=costnod+cost[nod][i];
				coada.push(lista[nod][i]);
			}
	}
	for(int i=2;i<=n;i++)
		printf("%d ",dist[i]);
}

int main(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	citire();
	bellman();
	return 0;
}