//Dijkstra cu arbori de intervale

#include <fstream>
#include <iostream>
#include <vector>
#define infinit 1<<29


using namespace std;

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

struct muchie{
	int nod;
	int cost;
};
vector <muchie> lista[50009];
int arb[200000];
int costuri[50009];
int viz[50009];
int n,m;

void get_data(){
	in>>n>>m;
	for (int i=1;i<=m;i++){
		int a;
		muchie x;
		in>>a>>x.nod>>x.cost;
		lista[a].push_back(x);
	}
}

void build(int nod,int st,int dr){
	if (st==dr) {
		if (st==1) arb[nod]=0;
		else
			arb[nod]=infinit;
		costuri[st]=infinit;
	}else{
		int mij=(st+dr)/2;
		int fs=2*nod;
		int fd=2*nod+1;
		build(fs,st,mij);
		build(fd,mij+1,dr);
		if (arb[fs]<arb[fd]) arb[nod]=arb[fs];
						else arb[nod]=arb[fd];
	}
}

void refresh(int nod, int st, int dr, int x, int val){
	if (st==dr){
		arb[nod]=val;
	}
	else
	{
		int mij=(st+dr)/2;
		int fs=2*nod;
		int fd=2*nod+1;
		if (x<=mij) refresh(fs,st,mij,x,val);
		else refresh(fd,mij+1,dr,x,val);
		if (arb[fs]<arb[fd]) arb[nod]=arb[fs];
		else arb[nod]=arb[fd];
	}
}

int get_minim(int nod, int st, int dr){
	if (st==dr) return st;
	else
	{
		int mij=(st+dr)/2;
		int fs=2*nod;
		int fd=2*nod+1;
		if (arb[fs]<arb[fd]) return get_minim(fs,st,mij);
		else return get_minim(fd,mij+1,dr);
	}
}
void print_data(){
	for (int i=2;i<=n;i++)
		if (costuri[i]!=infinit)
		out<<costuri[i]<<' ';
		else out<<"0";
}

int main(){
	get_data();
	build(1,1,n);
	while (arb[1]!=infinit){
		int who=get_minim(1,1,n);
		costuri[who]=arb[1];
		viz[who]=1;
		for (int i=0;i<lista[who].size();i++){
			muchie x=lista[who][i];
			if (viz[x.nod]==0 && x.cost+costuri[who]<costuri[x.nod]){
				costuri[x.nod]=x.cost+costuri[who];
				refresh(1,1,n,x.nod,costuri[x.nod]);
			}
		}
		refresh(1,1,n,who,infinit);
	}
	/*for (int i=1;i<=n;i++){
		for (int j=0;j<lista[i].size();j++)
			cout<<lista[i][j].nod<<' '<<lista[i][j].cost<<' ';
			cout<<'\n';
		}*/
	print_data();
	return 0;
}