#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <queue>

const int MAX = 2001;

using namespace std;

int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	int n, m, i;
	f>>n>>m;
	map<int, vector< pair<int, int> > > outbound;
	map<int, int> distances;
	map<int, bool> visited;
	
	for (i = 1; i <= n; i++){
		distances[i] = MAX;
		visited[i] = false;
	}
	
	for (i = 0; i < m; i++){
		int a, b, c;
		f>>a>>b>>c;
		outbound[a].push_back(make_pair(b, c)); 
	}
	f.close();
	
	
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> >  > qu;
	qu.push( make_pair(1, 0) );
	distances[1] = 0;
	
	pair <int, int> c;
	
	while (! qu.empty() ){
		c = qu.top();
		qu.pop();
		visited[ c.first ] = true;
		
		vector< pair<int, int> > v = outbound[c.first];
		for ( vector< pair<int, int> >::iterator it = v.begin(); it != v.end(); ++it){
			pair<int, int> p = *it;
			//if (visited[p.first]) continue;
			//cout<<c.first<<" "<<p.second<<" "<<distances[p.first]<<endl;
			if ( distances[c.first] + p.second < distances[p.first] ){
				distances[p.first] = distances[c.first] + p.second;
				qu.push( make_pair(p.first, distances[p.first] ) ); 
			}
			//cout<<p.first<<"  "<<p.second<<endl;
		}
		
		//cout<<c.first<<" "<<c.second<<endl;
	}
	
	
	//return 0;
	for (i = 2; i <= n; i++)
		if (distances[i] == MAX ) g<<"0 ";
		else g<<distances[i]<<" ";
	g.close();
	
	return 0;
}