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

#define Inf numeric_limits<int>::max()

using namespace std;
using Graph = vector<vector<pair<int, int> > >;

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

void find_min_road(Graph& G, vector<int>& distances, int source, int N)
{
    queue<int> Q;
    vector<int> visited(N + 1, 0);

    Q.push(source);
    visited[source] = 1;
    distances[source] = 0;

    while (!Q.empty()) {
        int currNode = Q.front();
        Q.pop();
        visited[currNode] = 0;

        for (auto &node : G[currNode]) {
            if (distances[currNode] + node.second < distances[node.first]) {
                distances[node.first] = distances[currNode] + node.second;
            
                if (!visited[node.first]) {
                    Q.push(node.first);
                    visited[node.first] = 1;
                }
            }
        }
    }
}

int main()
{
    int N, M;
    in >> N >> M;

    Graph G(N + 1);
    int x, y, c;
    for (int i = 1; i <= M; i++) {
        in >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    vector<int> distances(N + 1, Inf);
    find_min_road(G, distances, 1, N);

    for (int i = 2; i <= N; i++)
        (distances[i] == Inf) ? out << "0 " : out << distances[i] << " ";

    out << '\n';

    return 0;
}