#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <functional>
#include <limits>

using namespace std;

template <class T>
class Graph {
    unordered_map<T, vector<pair<T, int>>> neighbors;
    vector<T> nodes;

public:
    template <class Iterator>
    Graph(Iterator begin, Iterator end):
	nodes(begin, end) {}

    void add_edge(T src, T dst, int cost = 1) {
	neighbors[src].push_back(make_pair(dst, cost));
    }

    /**@brief Find the single-source shortest paths
     *
     * Uses Dijkstra's algorithm.
     */
    unordered_map<T, int> dijkstra(T src) {
	const int inf = numeric_limits<int>::max() / 2 - 1;

	auto comp = [](const pair<int, T>& fst, const pair<int, T>& scd) {
	    return fst.first > scd.first;
	};
	
	priority_queue<pair<int, T>, vector<pair<int, T>>, decltype(comp)> q(comp);
	unordered_map<T, int> dist;

	q.push(make_pair(0, src));
	for (auto node : nodes) {
	    if (node != src) {
		q.push(make_pair(inf, node));
		dist[node] = inf;
	    }
	}

	while (!q.empty()) {
	    auto p = q.top(); q.pop();

	    for (auto next : neighbors[p.second]) {
		if (p.first + next.second < dist[next.first]) {
		    dist[next.first] = p.first + next.second;
		    q.push(make_pair(dist[next.first], next.first));
		}
	    }
	}

	return dist;
    }
};

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n, m;
    fin >> n >> m;
    vector<int> nodes;
    for (int i = 1; i <= n; ++i)
	nodes.push_back(i);
    
    Graph<int> g(nodes.begin(), nodes.end());
    for (int i = 0; i < m; ++i) {
	int src, dst, cost;
	fin >> src >> dst >> cost; 
	g.add_edge(src, dst, cost);
    }

    auto result = g.dijkstra(1);
    for (int i = 2; i <= n; ++i) {
	fout << result[i] << " ";
    }
    fout << endl;
    
    return 0;
}