#include<iostream.h>
#include<fstream.h>
int inf=32000,a[100][100],n,d[100],p[100];
void dijkstra (int x)
{int i,min,k,ok;
int viz[100];
for(i=1;i<=n;i++)
{d[i]=a[x][i];
if(d[i]!=inf)
p[i]=x;
else
p[i]=0;
viz[i]=0;}
viz[x]=1;
ok=1;
while(ok==1)
{min=inf;
for(i=1;i<=n;i++)
if(viz[i]==0&&min>d[i])
{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()
{int x,y,c,i,m,j;
ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
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>>c;
a[x][y]=c;}
dijkstra(1);
for(i=2;i<=n;i++)
	h<<d[i]<<" ";
	return 0;}