#include <fstream.h>
#include <vector>
#include <list>

using namespace std;
int n,m,d[50000],u[50000];
const long inf = 100000000;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
vector<list<pair<int,int> > >v;
list<pair<int,int> >::iterator it;


void citire(){
	fi>>n;
	fi>>m;
	v.resize(n+1);
	int i,j,k,c;
	for(i=1;i<=n;i++)
		v[i].push_back(pair<int,int>(0,0));
	for(k=1;k<=m;k++){
		fi>>i;
		fi>>j;
		fi>>c;
		v[i].push_back(pair<int,int>(j,c));
		v[i].begin()->first++;
	}
	fi.close();
}

void afisare(){
	int i;
	for(i=2;i<=n;i++)
		fo<<d[i]<<" ";
	fo<<'\n';
	fo.close();
}

void dijkstra(){
	long min;
	int i,nod;
	for(i=2;i<=n;i++)
		d[i]=inf;
	u[1]=1;
	it=v[1].begin();
	it++;
	for(;it!=v[1].end();++it)
		d[it->first]=it->second;
	
	while(1){
		min=inf;
		nod = -1;
		for(i=1;i<=n;i++)
			if(!u[i] && min>d[i]){
				min=d[i];
				nod=i;
			}
		
		u[nod]=1;
		if(min==inf)
			break;
		
		it=v[nod].begin();
		++it;
		for(;it!=v[nod].end();++it)
			if(d[it->first]>d[nod]+it->second)
				d[it->first]=d[nod]+it->second;
		/*for(i=1;i<=v[nod][0].first;i++)
			if(d[v[nod][i].first]>d[nod]+v[nod][i].second)
				d[v[nod][i].first]=d[nod]+v[nod][i].second;*/
	}
	for(i=2;i<=n;i++)
		if(d[i]==inf)
			d[i]=0;
}	


int main(){
	citire();
	dijkstra();
	afisare();
	return 0;
}