#include<fstream>
#include<vector>
#include<iostream>
#include<stdlib.h>
#define lmic 51000
#define infinit 1000000
using namespace std;

struct muchie{
	int inf;
	int cost;
}y;
vector<muchie>v[lmic];
int d[lmic];
int prezent[lmic];
int coada[1000000];
int aparitii[lmic];
ofstream g("bellmanford.out");

int bellmanford(int n){
	int prim,ultim,i,j,x,y;
	for(i=2;i<=n;i++)
		d[i]=infinit;
	ultim=1;
	prim=1;
	coada[1]=1;
	while(prim<=ultim){
		x=coada[prim++];
		aparitii[x]++;
		for(i=0;i<v[x].size();i++)
				if(d[v[x][i].inf]>d[x]+v[x][i].cost)
					if(prezent[v[x][i].inf]==0){
						coada[++ultim]=v[x][i].inf;
						aparitii[v[x][i].inf]++;
						d[v[x][i].inf]=d[x]+v[x][i].cost;
						if(aparitii[v[x][i].inf]>n){
						g<<"Ciclu negativ!";
						return 0;
						}
					}
	}
	return 1;
}
		
	
int main(){
	ifstream f("bellmanford.in");
	int i,n,m,a;
	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>a>>y.inf>>y.cost;
		v[a].push_back(y);
	}
	if(bellmanford(n)==1)
		for(i=2;i<=n;i++)
			g<<d[i]<<" ";
}