#include <cstdio>
#define nmax 1001
#define infinit 100000

using namespace std;

int c[nmax][nmax];
int fol[nmax];//care noduri au costul minim calculat
long d[nmax]; //d[i]=costul drumului de la 1 la d[i]
int n,m;

void citire()
{
	int x,y,cost,i,j;
	scanf("%d%d",&n,&m);
	fol[1]=1;
	d[1]=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			c[i][j]=infinit;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&cost);
		c[x][y]=cost;
	}
	for(i=2;i<=n;i++)
		d[i]=c[1][i];
}

void afisare()
{
	for(int i=2;i<=n;i++)
        printf("%d ",d[i]);
	printf("\n");
}

void dijkstra()
{
	int i,j,minim,poz;
	for(i=2;i<=n;i++) //n-1 pasi
	{
		minim=infinit;
		for(j=1;j<=n;j++)
			if(d[j]<minim && fol[j]==0)
			{
				minim=d[j];
				poz=j;
			}
		fol[poz]=1;
		for(j=1;j<=n;j++)
			if(fol[j]==0 && d[j]>minim+c[poz][j])
				d[j]=minim+c[poz][j];
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra();
	afisare();
	return 0;
}