#include<iostream.h>
#include<fstream.h>
ofstream h("dijkstra.out");
long long d[10000],n,a[10000][10000];
long long p[10000],inf=1000000;
int viz[100];
void dijk(int x)
{long long i;
long long ok=1,k,min;
for(i=1;i<=n;i++)
{d[i]=a[x][i];
if(d[i]!=inf)
	p[i]=x;}
viz[x]=1;
while(ok==1)
{min=inf;
for(i=1;i<=n;i++)
	if(d[i]<min&&viz[i]==0)
{min=d[i];
k=i;}
if(min!=inf)
	{viz[k]=1;
for(i=1;i<=n;i++)
	if(viz[i]==0&&d[i]>d[k]+a[k][i])
	{d[i]=d[k]+a[k][i];
	p[i]=k;}}
	else
	ok=0;}}
int main()
{long long x,y,m,i,j,o;
	ifstream f("dijkstra.in");	
f>>n>>m;
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		a[i][j]=inf;
for(i=1;i<=m;i++)
{f>>x>>y>>o;
	a[x][y]=o;
}
dijk(1);
for(i=2;i<=n;i++)
	h<<d[i]<<" ";
return 0;}