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

#define MAX_N 50005

struct Edge {
    int to, cost;
    Edge(int to, int cost) : to{to}, cost{cost} {}
};

struct Node {
    int id, dist;

    Node(int id, int dist) : id{id}, dist{dist} {}

    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

std::vector<Edge> adj[MAX_N];
int dist[MAX_N];
bool visited[MAX_N];

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

    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, cost;
        fin >> u >> v >> cost;
        adj[u].push_back(Edge(v, cost));
    }

    for (int i = 1; i <= n; i++) {
        dist[i] = std::numeric_limits<int>::max();
    }

    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;

    dist[1] = 0;
    pq.push(Node(1, 0));

    while (!pq.empty()) {
        auto current = pq.top();
        pq.pop();

        if (visited[current.id]) {
            continue;
        }

        visited[current.id] = true;


        for (auto e : adj[current.id]) {
            if (dist[current.id] + e.cost < dist[e.to]) {
                dist[e.to] = dist[current.id] + e.cost;
                pq.push(Node(e.to, dist[e.to]));
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (dist[i] == std::numeric_limits<int>::max()) {
            fout << 0;
        } else {
            fout << dist[i];
        }

        if (i < n) {
            fout << " ";
        }
    }

    fout << "\n";
    return 0;
}