#include <fstream>
#include <queue>
#include <vector>

using namespace std ;

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

class cmp {
	public :
	bool operator ()(const pair<int, int> &a, const pair<int, int> &b) const {
		return a.second > b.second ;
	}
};

int main(int argc, char const *argv[])
{
	int n, m ;
	cin >> n >> m ;
	vector <pair<int, int>> *gr = new vector <pair<int, int>> [n + 1] ; 
	while (m --){
		int x, y , cost ; 
		cin >> x >> y >> cost ; 
		gr [x].push_back ({y, cost}) ;
	}
	priority_queue <pair<int, int>, vector<pair<int, int>>, cmp> H ;
	vector <int> dist (n + 1, 1e9) ;
	dist[1] = 0 ;
	H.push({1, 0}) ;
	while (!H.empty()) {
		pair<int, int> cur = H.top() ; 
		H.pop() ;

		if (dist[cur.first] != cur.second) {
			continue ;
		}
		for (auto x : gr [cur.first]) {
			if (dist [x.first] > dist [cur.first] + x.second) {
				dist [x.first] = dist [cur.first] + x.second ;
				H.push ({x.first, dist [x.first]}) ;
			}
		}
	}
	for (int i = 2 ; i <= n ; ++ i) {
		if (dist [i] == (int)(1e9)) {
			cout << 0 << ' ' ; 
		}
		else {
			cout << dist [i] << ' ' ;
		}
	}
	return 0;
}