#include<iostream>
#include<fstream>
using namespace std;
struct node{
node *adr;
int dest;
int length;
};
int a[5000][5000];
int shortest[50000];
int main(){
int q,b,x,i,j,n,m;	
ifstream f("data.in");
f>>n>>m;
for (i=1; i<=n; i++)
	for (j=1; j<=n; j++)
		a[i][j]=-1;
for (i=1; i<=m; i++)
{f>>q>>b>>x; a[q][b]=x;}

for (i=1; i<=n; i++) { shortest[i]=2000000; }
	shortest [1]=0;
for (i=1; i<=n; i++)
	for (j=1; j<=n; j++)
		if (a[i][j]!=-1 && a[i][j]+shortest[i]<shortest[j]) 
			shortest[j]=shortest[i]+a[i][j];
	
	
for (i=1; i<=n; i++)
{cout<<shortest[i]<<" ";
}	
	
return 0;
}