#include <stdio.h>
#define dim 1000
#define inf 250000

int n,m,ct;
unsigned int a[dim][dim];
unsigned int viz[dim],par[dim];
unsigned long cost[dim];

//--------------
void tip()
{
freopen("dijkstra.out","w",stdout);
for (int i=1;i<n;i++)
	if (cost[i]==inf)
		printf("%d ",0);
	else
		printf("%ld ",cost[i]);
}
//--------------
void cit()
{
int x,y,val;
freopen("dijkstra.in","r",stdin);
scanf("%d %d",&n,&m);
for (int i=0;i<m;i++)
{
	scanf("%d %d %d",&x,&y,&val);
	a[x-1][y-1]=val;
}
}
//---------------
void djk(int nod)
{
unsigned long cmin=inf;
int urm=0;
ct++;
viz[nod]=1;
for (int i=1;i<n;i++)
{
	if (viz[i]==0)
	{
		if ((cost[i]>a[nod][i]+cost[nod])&&(a[nod][i]!=0))
		{
			cost[i]=a[nod][i]+cost[nod];
			par[i]=nod;
		}
		if (cmin>cost[i])
		{
			cmin=cost[i];
			urm=i;
		}
	}
}
if (ct<n-2)
djk(urm);
}
//-------------
void ini()
{
int urm=0;
unsigned long cmin=inf;
for (int i=1;i<n;i++)
{
	if (a[0][i]!=0)
	{
		cost[i]=a[0][i];
		par[i]=0;
		if (cmin>cost[i])
		{
			urm=i;
			cmin=cost[i];
		}
	}
	else
		cost[i]=inf;
}
viz[0]=1;
cost[0]=0;
par[0]=0;
djk(urm);
}
//-------------
int main()
{
cit();
ini();
tip();
return 0;
}