#include<fstream>
#include<iostream>
using namespace std;

#define MAX_N 50001
#define INFINIT 234235

struct nod
{
	int capat,cost;
	nod *next;
}*G[MAX_N];

long n,m,d[MAX_N],t[MAX_N];

void adauga_arc(int x,int y,int c)
{
	nod *p;        p=new nod;
	p->capat=y;    p->cost=c;
    p->next=G[x];  G[x]=p;
}	

void citire(void)
{
	fstream f("dijkstra.in",ios::in);
	int i,x,y,c;
	f>>n>>m;
	for(i=1; i<=m; i++)
	{
		f>>x>>y>>c;
		adauga_arc(x,y,c);
	}
	f.close();
}

int bellman_ford(int start)
{
	int i,j,c,aparitii[MAX_N]={0},vizitat[MAX_N]={0};
	nod *st,*dr;
	
	st=dr=new nod; 
	st->capat=start;
	st->next=NULL; 
	
	
	for(i=1; i<=n; i++)
		d[i]=INFINIT;
	d[start]=0;
	while(st)
	{
		i=st->capat;    
        vizitat[i]=0;		
		for(nod *p=G[i]; p!=NULL; p=p->next)
		{
			j=p->capat;
			c=p->cost;
			if(d[j]>d[i]+c) 
			{
				d[j]=d[i]+c;
				if(vizitat[j]==0) 
				{
					vizitat[j]=1; 
					if(aparitii[j]>n)
						return 0;
					aparitii[j]++;
				
					nod *t=new nod;
					t->capat=j;
					t->next=NULL;
					dr->next=t;
					dr=dr->next;
				}
			}
		}
		
		nod *t=st;
		st=st->next;
		delete t;
	}
	
	
	return 1;
}

void afisare(void)
{
	fstream g("dijkstra.out",ios::out);
	int i;
	if(bellman_ford(1))
		for(i=2; i<=n; i++)
			if(d[i]==INFINIT)
				g<<"0"<<" ";
			else
				g<<d[i]<<" ";
	else
		g<<"Eroare!Exista ciclu negativ!";
	g.close();
}

int main()
{
	citire();
	afisare();
	return 0;
}