#include<stdio.h>
#include<limits.h>
#include<vector>
#include<queue>
#include<algorithm>
#define NMAX 50000
using namespace std;
int N,M,D[NMAX+3],APARITII[NMAX+3];
vector<pair<int,int> >VECINI[NMAX];
queue<int>COADA;
int minim(int x,int y)
{if(x<y) return x; return y;}
void deschidere()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
}
void initializare()
{
	for(int i=2;i<=N;i++)
		D[i]=INT_MAX;
}
void citire()
{
	int X,Y,C;
	scanf("%d%d",&N,&M);
	while(M--)
	{
		scanf("%d%d%d",&X,&Y,&C);
		VECINI[X].push_back(make_pair(Y,C));
	}
}
void bellmanford()
{
	COADA.push(1);
	APARITII[1]++;
	while(COADA.size())
	{
		int i,nod=COADA.front();
		int lungime=VECINI[nod].size();
		for(i=0;i<lungime;i++)
			if(D[nod]+VECINI[nod][i].second<D[VECINI[nod][i].first])
			{
				D[VECINI[nod][i].first]=D[nod]+VECINI[nod][i].second;
				COADA.push(VECINI[nod][i].first);
				APARITII[VECINI[nod][i].first]++;
				if(APARITII[VECINI[nod][i].first]>N)
				{
					printf("Ciclu negativ!\n");
					return ;
				}
			}
			COADA.pop();
	}
}
void afisare()
{
	for(int i=2;i<=N;i++)
		printf("%d ",D[i]);
}
int main()
{
	deschidere();
	citire();
	initializare();
	bellmanford();
	afisare();
	return 0;
}