#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
const int INF = 1000000000;

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

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

int N, M;

vector< vector<pair<int, int> > > edges;
priority_queue< pair<int,int>, vector<pair<int,int> >, Compare> Q;
bool selected[50001];
int parent[50001];
int distances[50001];

void dijkstra(){
	int S = 1;
	
	
	for (int i = 2; i <= N; ++i) {
		distances[i] = INF;
		parent[i] = -1;
		Q.push(make_pair(i, distances[i]));
	}
	distances[S] = 0;
	Q.push(make_pair(S, 0));

	while(Q.size() != 0){
		pair<int,int> getPair = Q.top();
		Q.pop();
		int u = getPair.first;
		//cout << u << "\n";

		if(selected[u]){
			continue;
		}
		selected[u] = true;

		for (int i = 0 ; i < edges.at(u).size(); ++i) {
			auto neigh = edges.at(u).at(i);
			int v = neigh.first;
			int lengthUV = neigh.second;
			if (selected[v]) {
				continue;
			}
			int alt = 0;
			if (distances[u] != INF) {
				alt = distances[u] + lengthUV;
				if (alt < distances[v]) {
					distances[v] = alt;
					parent[v] = u;
					Q.push(make_pair(v, distances[v]));
				}
			}
		}
	}
	for (int i = 2; i <= N; ++i) {
			if (distances[i] == INF) {
				g << "0 ";
			} else {
				g << distances[i] << " ";
			}
	}

}


void read(){
	int start, end , cost;
	f >> N >> M;
	for(int i = 0 ; i<= N ; ++i){
		edges.push_back(vector<pair<int,int> >());
	}
	for(int i = 0 ; i < M ; ++i){
		f >> start >> end >> cost;
		edges.at(start).push_back(make_pair(end,cost));
	}
}

int main(){
	read();
	dijkstra();
	return 0 ;
}