#include<fstream>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 50010
const int inf = 0x3f3f3f3f; 
using namespace std;
vector< pair<int,int> > e[maxn];
bool test[maxn];
queue<int> Q;
int N,M;
long d[maxn];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void bellman(int S){
	for(int i=1;i<=N;i++)
		d[i]=inf;
	memset(test,false,maxn);
	d[S]=0;
	test[S]=true;
	Q.push(S);
	while(!Q.empty()){
		int nod=Q.front();
		Q.pop();
		test[nod]=false;
		for(vector< pair<int,int> >::iterator it=e[nod].begin();it!=e[nod].end();++it){
			if(d[it->first]>d[nod]+it->second){
				d[it->first]=d[nod]+it->second;
				if(!test[it->first])
					Q.push(it->first),test[it->first]=true;
			}
		}
	}
}
			
void citire(){
	int x,y,c;
	f>>N>>M;
	for(int i=1;i<=M;i++){
		f>>x>>y>>c;
		e[x].push_back(make_pair(y,c));
	}
}

int main(){
	citire();
	bellman(1);
	for(int i=2;i<=N;i++)
		g<<d[i]<<' ';
	g<<'\n';
	g.close();
	return 0;
}