#include<cstdio>
using namespace std;

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

long s,n,a[5000][5000],d[50000],t[50000],q[50000],inf=2000000000;



void dijkstra()
{
	q[s]=1;
	for (int i=1;i<=n;i++)
		{if (a[s][i])
			d[i]=a[s][i];
		 if (!a[s][i]&&i!=s)
			d[i]=inf;
		}
		
int min=inf;
int nod,o=1;

while(o)
	{ 
		min=inf;

	for (int i=1;i<=n;i++)
	   if (!q[i]&&d[i]<min)
				{ min=d[i];
				   nod=i;}
	
				q[nod]=1;			
	if (min==inf) o=0;
	
	for (int i=1;i<=n;i++)
		if (!q[i]&&d[i]>d[nod]+a[nod][i]&&a[nod][i])
			{ d[i]=d[nod]+a[nod][i];
		      t[i]=nod;
			}
	}
}




int main()
{int m;
	fscanf(f,"%d%d",&n,&m);
	
	for (int i=1;i<=m;i++)
	{  int x,y,c;
	fscanf(f,"%d%d%d",&x,&y,&c);
	a[x][y]=c;
	}
	
	s=1;
	dijkstra();
	
	
	for (int i=2;i<=n;i++)
		fprintf(g,"%d ",d[i]);
	
	
return 0;}