#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define lmax 50013
#define inf 0xfffffff
vector<pair<int,int> >vv[lmax];
pair<int,int>hh[lmax];
int n,m,dd[lmax],pp[lmax],k;

void push(pair<int,int> c){
	int t,f;
	if(pp[c.second]){
		f=pp[c.second];
		hh[f]=c;} else {
		hh[++k]=c;
		f=k;
		pp[hh[k].second]=k;
	}
	t=f/2;
	while(t>0 && hh[t].first>hh[f].first){
		swap(hh[t], hh[f]);
		swap(pp[hh[t].second],pp[hh[f].second]);
		f=t; t=f/2;
	}
}

int pop(){
	int t,f,x=hh[1].second;
	hh[1]=hh[k--];
	pp[hh[1].second]=1;
	t=1; f=2;
	if(k>f && hh[f+1].first<hh[f].first)f++;
	while(f<k && hh[t].first>hh[f].first){
		swap(hh[t], hh[f]);
		swap(pp[hh[t].second],pp[hh[f].second]);
		t=f; f=2*t;
		if(k>f && hh[f+1].first<hh[f].first)f++;
	}
	return x;
}

void dst(){
	int x,l;
	for(int i=1;i<=n;i++) dd[i]=inf;
	dd[1]=0;
	push(make_pair(0,1));
	while(k>0){
		x = pop(); l = vv[x].size();
		for(int i=0;i<l;i++)
			if(dd[vv[x][i].second]>dd[x]+vv[x][i].first)
			{
				dd[vv[x][i].second]=dd[x]+vv[x][i].first;
				push(make_pair(dd[vv[x][i].second],vv[x][i].second));
			}
	}
}

int main(){
	int x,y,z;
	f>>n>>m;
	for(int i=0;i<m;i++){
		f>>x>>y>>z;
		vv[x].push_back(make_pair(z,y));
	}
	dst();
	for(int i=2;i<=n;i++)
		if(dd[i]==inf)g<<"0 "; else g<<dd[i]<<" ";
	
	return 0;
}