#include <fstream>
#include <vector>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int const N=1<<16;
int const INF=1<<10;

int n,m,u=0,p=0;
int costf[1<<18];

struct nod{
	int v,cost;
};

vector <nod> a[N];

int coada[1<<18];

int min(int x,int y){
	if(x<y)
		return x;
	return y;
}

void BF(){
	int x,i,y,c;
	u++;
	coada[u]=1;
	p++;
	while(p<=u){
		x=coada[p++];
		for(i=0;i<a[x].size();i++){
			y=a[x][i].v;
			c=a[x][i].cost;
			if(costf[x]+c>=costf[y])
				continue;
			u++;
			coada[u]=a[x][i].v;
			costf[a[x][i].v] = costf[x]+a[x][i].cost;
		}
	}
}

int main(){
	int x,y,z,i;
	nod aux;
	in>>n>>m;
	while(m--){
		in>>x>>y>>z;
		aux.v=y;
		aux.cost=z;
		a[x].push_back(aux);
	}
	for(i=2;i<=n;i++){
		costf[i]=INF;
	}
	BF();
	for(i=2;i<=n;i++){
		if(costf[i]==INF){
			out<<"0 ";
		}
		else{
			out<<costf[i]<<" ";
		}
	}
	return 0;
}