#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int main(){
	int n, m;
	f >> n >> m;

	vector < vector < pair < int, int > > > graf(n+1);
	vector < int > dist(n+1, n*20000);
	vector < int > viz(n+1, 0);
	set < pair<int, int> > S;
	S.insert(make_pair(0, 1));

	for(int i = 0; i < m; i++){
		int x, y, cost;
		f >> x >> y >> cost;
		graf[x].push_back(make_pair(y, cost));
	}
    dist[1] = 0;
	while(!S.empty()){

		int poz = (*S.begin()).second;
		for(auto muchie: graf[poz]){
			if(muchie.second + dist[poz] < dist[muchie.first])
            {
                S.erase(make_pair(dist[muchie.first], muchie.first));
                dist[muchie.first] = muchie.second + dist[poz];
                S.insert(make_pair(dist[muchie.first], muchie.first));
            }
		}
		S.erase(S.begin());
	}

	for(int i = 2; i <= n; i++)
        if(dist[i]!=n*20000) g << dist[i] << ' ';
            else g << "0 ";

	return 0;
}