#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define maxn 50005
#define infinit 1<<30
struct graf
	{	int nod,cost;	};
graf *a[maxn];
int grad[maxn];
int d[maxn],h[maxn],poz[maxn];
int n,vf;

	void citire(void)
	{	FILE *fin=fopen("dijkstra.in","r");
		int x,y,c,m;
		fscanf(fin,"%d%d",&n,&m);
		for(; m; m--)
		{	fscanf(fin,"%d%d%d",&x,&y,&c);
			a[x]=(graf*)realloc(a[x], (grad[x]+1)*sizeof(graf));
			a[x][grad[x]].nod=y; a[x][grad[x]].cost=c;
			grad[x]++;
		}
		fclose(fin);
	}
	
	void upheap(int fiu)
	{	int tata=fiu>>1,v=h[fiu];
		while(tata && d[ h[tata] ]>d[v])
		{	h[fiu]=h[tata]; poz[ h[tata] ]=fiu; 
			fiu=tata; tata=fiu>>1;
		}
		h[fiu]=v; poz[v]=fiu;
	}
	
	void downheap(int tata)
	{	int fiu=tata<<1,v=h[tata];
		while(fiu<=vf)
		{	if(fiu<vf && d[ h[fiu] ]>d[ h[fiu+1] ]) fiu++;
			if(d[ h[fiu] ]<d[v])
			{	h[tata]=h[fiu]; poz[ h[fiu] ]=tata;
				tata=fiu; fiu=tata<<1;
			}
			else fiu=vf+1;
		}
		h[tata]=v; poz[v]=tata;
	}
	
	int extragemin(void)
	{	int r=h[1];
		h[1]=h[vf--];
		downheap(1);
		return r;
	}
	
	void dijkstra(void)
	{	int i,min,u;
		for(i=2;i<=n;i++) d[i]=infinit, poz[i]=-1;
		d[1]=0; h[1]=1; poz[1]=1; vf=1;
		while(vf)
		{	min=extragemin();
			for(i=0;i<grad[min];i++)
			{	u=a[min][i].nod;
				if(d[u]>d[min]+a[min][i].cost)
				{	d[u]=d[min]+a[min][i].cost;
					if(poz[u]!=-1) upheap(poz[u]);
					else h[++vf]=u, poz[u]=vf; upheap(vf);
				}
			}
		}
	}
	
	void scrie(void)
	{	FILE *fout=fopen("dijkstra.out","w");
		for(int i=2;i<=n;i++) fprintf(fout,"%d ", (d[i]<infinit ? d[i]:0) );
		fclose(fout);
	}
	
int main(void)
{	citire();
	dijkstra();
	scrie();
	return 0;
}