#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];

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

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

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

void 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;
	for (p=v[1];p;p=p->next)
	{
		dist[p->info]=p->cost;
		h[++k]=p->info;
		poz[p->info]=k;
		urca (k);
	}
	
	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) 
			{
				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("dijkstra.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 ();
	djikstra ();
	afisare ();
	return 0;
}