// Algoritmul Bellman-Ford.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("bellmanford.in", "r");
FILE *g=fopen("bellmanford.out", "w");

int n, m;

typedef struct nod
{
	int x, d;
	struct nod *adr;
};

nod *l[50001];

int sol[50001];
int coada[1000001];
int cd;
int incd[50001];
int cntin[1000001];
int neg;

void add(int x, int y, int d)
{
	nod *p=new nod;
	p->x=y;
	p->d=d;
	p->adr=l[x];
	l[x]=p;
}

void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y, d;
		fscanf(f, "%d%d%d", &x, &y, &d);
		add(x, y, d);
	}
}

void init()
{
	for (int i=1; i<=n; i++)
	{
		sol[i]=10000000;
	}
	sol[1]=0;
}

void program()
{
	coada[++cd]=1;
	int i=1;
	while (i<=cd)
	{
		incd[coada[i]]=0;
		nod *p=l[coada[i]];
		while (p!=NULL)
		{
			if (sol[p->x]>sol[coada[i]]+p->d)
			{
				sol[p->x]=sol[coada[i]]+p->d;
				if (!incd[p->x])
				{
					if (cntin[p->x] > n)                       
					{
						neg = 1;                    
						fprintf(g, "Ciclu negativ!\n");
						return ;
					}
					else 
					{                                              
						cntin[p->x] ++; 
						coada[++cd]=p->x;
						incd[p->x]=1;
					}
				}
			}
			p=p->adr;
		}
		i++;
	}
	for (int k=2; k<=n; ++k)
		fprintf(g, "%d ", sol[k]);
}


int main()
{
	read();
	init();
	program();
	return 0;
}