#include<fstream.h>
#include<iostream.h>

const int inf=1<<30;

int a[3][100000],d[100000],sel[100000],i,j,n,m,av,ax,ac,ns;

int main()
{
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
fin>>n>>m;
ns=1;
for(i=1;i<=m;i++)fin>>a[0][i]>>a[1][i]>>a[2][i];
sel[ns]=1;
for(i=1;i<=n;i++)if(i!=ns)d[i]=inf;
for(i=1;i<n;i++)
	{
	for(j=1;j<=m;j++)if(d[a[1][j]]>d[a[0][j]]+a[2][j])d[a[1][j]]=d[a[0][j]]+a[2][j];
}

for(i=2;i<=n;i++)fout<<d[i]<<' ';
return 0;
}