#include<fstream>
#include<vector>
#include<set>
#define infinit 100000000
using namespace std;

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

int n, m, dist[50004];
vector <pair<int,int> > nod[50004];
set <int> stim;
set <int>::iterator minim;

int main(){
	cin>>n>>m;
	
	for(int i=1; i<=m; ++i){
		int a,b,c;
		cin>>a>>b>>c;
		nod[a].push_back(make_pair(b,c));
	}
	
	for(int i=1; i<=n; ++i){
		dist[i] = infinit;
	}
	dist[1] = 0;
	stim.insert(1);
	
	while(!stim.empty()){
		minim = stim.begin();
		int curent_nod = *minim;
		int curent_cost = dist[curent_nod];
		 stim.erase(minim);
	
	for(int i=0; i!=nod[curent_nod].size(); ++i){
		if(dist[nod[curent_nod].at(i).first]> curent_cost + nod[curent_nod].at(i).second){
								dist[nod[curent_nod].at(i).first] = curent_cost + nod[curent_nod].at(i).second;
		}
		stim.insert(nod[curent_nod].at(i).first);
	}
}
	for(int i=2; i<=n; ++i){
		if(dist[i]==infinit) dist[i]=0;
		cout<<dist[i]<<" ";
	}
	
	return 0;
}