#include<fstream.h>

#define inf 500000000 

struct nod { int info,cost; nod *next;};

nod *v[50005];

int m,n,k,dist[50005],h[50005],poz[50005],nr[50005];

void afisare ()
{
	int i;
	ofstream g("bellmanford.out");
	for (i=2;i<=n;i++)
		if (dist[i]==inf) 
			g<<0<<' ';
		else
			g<<dist[i]<<' ';
	g.close();
}

void urca (int k)
{
	int x=k;
	while (x>1 && dist[h[x]]<dist[h[k>>1]])
	{
		poz[h[x]]=x>>1;
		poz[h[x>>1]]=x;
		h[x]=(h[x]^h[x>>1])^(h[x>>1]=h[x]);
		x>>=1;
	}
}

void coboara ()
{
	int x=k,y=1;
	while (x!=y)
	{
		x=y;
		if (x*2 <=k && dist[h[x]]>dist[h[x*2]]) y=x*2;
		if (x*2+1<=k && dist[h[y]]>dist[h[1+x*2]]) y=x*2+1;
		poz[h[x]]=y;
		poz[h[y]]=x;
		h[x]=(h[x]^h[y])^(h[y]=h[x]);
	}
}		

int  djikstra ()
{
	int i,min;
	nod *q,*p;
	for (i=2;i<=n;i++)
		dist[i]=inf;
	for (i=1;i<=n;i++)
		poz[i]=0;

	k=1;
	h[1]=1;
	poz[1]=1;
	nr[1]++;
	while (k)
	{
		min=h[1];
		poz[min]=0;
		h[1]=h[k--];
		poz[h[1]]=1;
		coboara();
		for (q=v[min];q;q=q->next)
			if (dist[q->info]>dist[min]+q->cost) 
			{
				nr[q->info]++;
				if (nr[q->info]>n) return 0;
				dist[q->info]=dist[min]+q->cost;
				if (poz[q->info])
					urca (poz[q->info]);
				else
				{
					poz[q->info]=++k;
					h[k]=q->info;
					urca (k);
				}
			}
	}
}	

void citire ()
{
	int i,x,y,c;
	nod *p;
	
	ifstream f("bellmanford.in");
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		p=new nod;
		p->info=y;
		p->cost=c;
		p->next=v[x];
		v[x]=p;
	}
	f.close();
}

int main()
{
	citire ();
	if (djikstra ()) afisare ();
		else
		{
				ofstream g("bellmanford.out");
				g<<"Ciclu negativ!";
		}
	return 0;
}