#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
#define NMax 50010
#define oo 0x3f3f3f3f
using namespace std;

const char IN[]="bellmanford.in",OUT[]="bellmanford.out";

int N,M;
int T[NMax],Visit[NMax];
bool inQue[NMax];
queue<int> qu;
vector<pair<int,int> > ad[NMax];

bool bellmanford()
{
	int x,i;
	qu.push(1);inQue[1]=true;

	for (i=1;i<=N;++i) T[i]=oo;
	T[1]=0;
	while (!qu.empty())
	{
		x=qu.front();qu.pop();inQue[x]=false;
		++Visit[x];
		if (Visit[x]>=N) return false;
		for (i=0;i<(int)ad[x].size();++i)
			if (T[x]+ad[x][i].second<T[ad[x][i].first]){
				T[ad[x][i].first]=T[x]+ad[x][i].second;
				if (!inQue[ad[x][i].first])
					qu.push(ad[x][i].first),
					inQue[ad[x][i].first]=true;
			}
	}
	return true;
}

int main()
{
	int x,y,c;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	while (M--){
		scanf("%d%d%d",&x,&y,&c);
		ad[x].push_back(make_pair(y,c));
	}
	fclose(stdin);

	bool b=bellmanford();

	freopen(OUT,"w",stdout);
	if (!b) printf("Ciclu negativ!");
	else
		for (int i=2;i<=N;++i) printf("%d ",T[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}