#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[lmic];
ofstream g("bellmanford.out");

void 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++];
		y=prezent[prim];
		for(i=0;i<v[x].size();i++)
				if((d[v[x][i].inf]>d[x]+v[x][i].cost)&&(prezent[v[x][i].inf]%2==0)){
					coada[++ultim]=v[x][i].inf;
					prezent[v[x][i].inf]++;
					d[v[x][i].inf]=d[x]+v[x][i].cost;
				}
		if(y!=prezent[prim])prezent[prim]++;
		if(prezent[prim]>n){
			g<<"Ciclu negativ!";
			exit(EXIT_SUCCESS);
		}
	}
}	
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);
	}
	bellmanford(n);
		for(i=2;i<=n;i++)
			g<<d[i]<<" ";
}