#include <bits/stdc++.h>

std::ifstream   input ("dijkstra.in");
std::ofstream   output("dijkstra.out");

#define num     int
#define num_mat std::vector <std::vector <std::pair <int, num>>>
#define num_INF 2000000005

class DEsopoPapeSolver {
public:
    DEsopoPapeSolver(num_mat& graph, int start) {
        dist.resize(graph.size(), num_INF);
        routine(graph, start);
    }

    num operator[] (int idx) const { return dist[idx]; }

protected:
    std::vector <num> dist;

private:
    void routine(num_mat& graph, int start) {
        dist[start] = 0;
        std::vector <int> classif(graph.size(), 2);
        std::deque  <int> deque;
        deque.push_back(start);

        while (!deque.empty()) {
            auto front = deque.front();
            deque.pop_front();
            classif[front] = 0;

            for (auto &edge:graph[front])
                if (dist[edge.first] > dist[front] + edge.second) {
                    dist[edge.first] = dist[front] + edge.second;
                    if (classif[edge.first] == 2)      classif[edge.first] = 1, deque.push_back(edge.first);
                    else if (classif[edge.first] == 0) classif[edge.first] = 1, deque.push_front(edge.first);
                }
        }
    }
};

int N, M;
num_mat graph;
inline void addEdge(int x, int y, num w) {
    graph[x].push_back({y, w});
}

int main()
{
    input >> N >> M;
    graph.resize(N);
    for (int i=0, x, y, w; i<M; ++i)
        input >> x >> y >> w, addEdge(--x, --y, w);

    DEsopoPapeSolver solver(graph, 0);
    for (int i=1; i<N; ++i)
        output << solver[i] << ' ';

    return 0;
}