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

struct muchie{
	int inf;
	int cost;
}y;
vector<int>minimum[2];
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 i,min=infinit-1,nod=-1,aux;
	for(i=0;i<minimum[1].size();i++)
		if(parcurs[minimum[1][i]]==0)
            if(min>D[minimum[1][i]]){
                min=D[minimum[1][i]];
                nod=minimum[1][i];
				aux=i;
            }
    if(nod!=-1)
		minimum[1].erase(minimum[1].begin()+aux,minimum[1].begin()+aux+1);
	return nod;
}

main(){
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,a;
register int i;
f>>n>>m;
for(i=2;i<=n;i++)
	minimum[1].push_back(i);
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();
}
for(i=2;i<=n;i++){
	if(D[i]!=infinit)g<<D[i]<<" ";
	else g<<0<<" ";
}
f.close();
g.close();
}