#include <fstream>
#include <vector>
#include <queue>
#include <climits>


using namespace std;


char const in_file[] = "dijkstra.in";
char const out_file[] = "dijkstra.out";


ifstream Read(in_file);
ofstream Write(out_file);


struct Node {
    uint32_t index;
    uint32_t cost;

    Node(uint32_t const, uint32_t const);
};


Node::Node(
    uint32_t const index,
    uint32_t const cost
) {
    this->index = index;
    this->cost = cost;
}


bool Compare(
    Node first,
    Node second
) {
    return first.cost > second.cost;
}


void ReadInput(
    vector<vector<Node>> &nodes
) {
    uint32_t n;
    uint32_t m;

    Read >> n;
    Read >> m;

    nodes.resize(n);

    uint32_t node1;
    uint32_t node2;
    uint32_t cost;

    for (; m; --m) {
        Read >> node1;
        Read >> node2;
        Read >> cost;

        --node1;
        --node2;

        nodes[node1].push_back(Node(node2, cost));
    }
}


void Dijkstra(
    vector<vector<Node>> const &nodes,
    vector<uint32_t> &dist,
    uint32_t const start_node
) {
    priority_queue<Node, vector<Node>, decltype(&Compare)> _queue(Compare);
    vector<bool> vis(nodes.size());
    uint32_t node;
    uint32_t neighbour;
    uint32_t neighbour_dist;

    dist[start_node] = 0;
    _queue.push(Node(start_node, dist[start_node]));
    vis[start_node] = true;

    while (_queue.size()) {
        node = _queue.top().index;
        _queue.pop();

        for (uint32_t i = 0; i < nodes[node].size(); ++i) {
            neighbour = nodes[node][i].index;
            neighbour_dist = dist[node] + nodes[node][i].cost;

            if (neighbour_dist < dist[neighbour]) {
                dist[neighbour] = neighbour_dist;

                if (vis[neighbour] == false) {
                    _queue.push(Node(neighbour, dist[neighbour]));
                    vis[neighbour] = true;
                }
            }
        }
    }
}


void Solve(
    vector<vector<Node>> const &nodes
) {
    vector<uint32_t> dist(nodes.size(), ULONG_MAX);

    Dijkstra(nodes, dist, 0);

    for (uint32_t i = 1; i < dist.size(); ++i) {
        if (dist[i] == ULONG_MAX) {
            Write << "0 ";
            return;
        }
        else {
            Write << dist[i] << ' ';
        }
    }
}


int main() {
    vector<vector<Node>> nodes;

    ReadInput(nodes);

    Solve(nodes);

    Read.close();
    Write.close();

    return 0;
}