#include<fstream.h>
ofstream g("dijkstra.out");
int v[10001][10001], i,j,n,m,p,viz[10001],d[10001],x,y,c,a,nr;

int selmin()
{int min=32001,b;
for(int k=1;k<=n;k++)
       if(!viz[k])
       if(d[k]<min)
		{min=d[k];
		 b=k;
		}
return b;
}




int main()
{ifstream f("dijkstra.in");

f>>n>>m;
p=1;
for(i=1;i<=m;++i)
	{f>>x>>y>>c;
	 v[x][y]=c;
	 if(c==0) v[x][y]=-1;
	 }
for(i=1;i<=n;++i)
	for(j=1;j<=n;j++)
		{if(i!=j && v[i][j]==0)
			v[i][j]=32000;
		if(v[i][j]==-1) v[i][j]=0;}
viz[p]=1;
for(i=1;i<=n;++i)

	 d[i]=v[p][i];

nr=1;
while(nr<n)
	{a=selmin();
	viz[a]=1;nr++;
	for(i=1;i<=n;++i)
		if(!viz[i])
			if(d[a]+v[a][i]<d[i])
				d[i]=d[a]+v[a][i];



	}
for(i=2;i<=n;i++)
	if(d[i]==32000) g<<"0 ";
	else g<<d[i]<<' ';
g<<'\n';

f.close();
g.close();
return 0;

}