#include<iostream>
#include<fstream>
#define inf 4000000
using namespace std;
long long s[50000],d[50000],t[50000],r,i,j,n,m,minim,poz,nod1,nod2,cost;
long long a[5000][5000];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{f>>n>>m;
r=1;
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{a[i][j]=inf;
		if(i==j)a[i][j]=0;
	}
	
	
for(i=1;i<=m;i++)
	{f>>nod1>>nod2>>cost;
	a[nod1][nod2]=cost;
	}
s[r]=1;
for(i=1;i<=n;i++)
{d[i]=a[r][i];
if(i!=r)
	if(d[i]<inf)t[i]=r;
}

for(i=1;i<=n-1;i++)
{minim=inf;
	for(j=1;j<=n;j++)
		if(s[j]==0)
			if(d[j]<minim)
			{minim=d[j];
			poz=j;
			}
			s[poz]=1;
			for(j=1;j<=n;j++)
				if(s[j]==0)
					if(d[j]>d[poz]+a[poz][j])
					{d[j]=d[poz]+a[poz][j];
					t[j]=poz;
					}

}


for(i=1;i<=n;i++)
	if(i!=r)
		if(d[i]==4000)g<<0<<" ";
		else g<<d[i]<<" ";



}