#include<fstream>
#include<vector>
#define infinit 2000000
using namespace std;

struct muchie{
	int inf;
	int cost;
}y;

vector<muchie>v[51000];
int D[51000];
int parcurs[51000];

void infiniteaza(int n){
	int i;
	D[1]=0;
	for(i=2;i<=n;i++)
		D[i]=infinit;
}

void parcurg(int a){
	int i;
	for(i=0;i<v[a].size();i++)
		if(D[a]+v[a][i].cost<D[v[a][i].inf])
			D[v[a][i].inf]=D[a]+v[a][i].cost;
		parcurs[a]=1;
		
}
int minim(int n){
	int i,min=infinit-1,nod=-1;
	for(i=n;i>=2;i--)
		if(parcurs[i]==0)
			if(min>D[i]){
				min=D[i];
				nod=i;
			}
	return nod;
}

main(){
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,a;
f>>n>>m;
for(i=1;i<=m;i++){
	f>>a>>y.inf>>y.cost;
	v[a].push_back(y);
}
a=1;
infiniteaza(n);
for(i=1;(i<=n)&&(a!=-1);i++){
	parcurg(a);
	a=minim(n);
}
for(i=2;i<=n;i++){
	if(D[i]!=infinit)g<<D[i]<<" ";
	else g<<0<<" ";
}
f.close();
g.close();
}