#include <fstream>
#include <string>
#include <vector>
#include <queue>

using namespace std;


struct Node {
    unsigned neighbour;
    unsigned cost;

    Node(unsigned const neighbour, unsigned const cost);
};


Node::Node(unsigned const neighbour, unsigned const cost) {
    this->neighbour = neighbour;
    this->cost = cost;
}


string const inFile = "dijkstra.in";
string const outFile = "dijkstra.out";

unsigned const MAXVAL = (1LL << 31) - 1;


ifstream _read(inFile);
ofstream _write(outFile);


void Read(unsigned &n, unsigned &m, vector<vector<Node>> &nodes) {
    _read >> n;
    _read >> m;

    nodes.resize(n);

    unsigned node1;
    unsigned node2;
    unsigned cost;

    for (unsigned i = 0; i < m; ++i) {
        _read >> node1;
        _read >> node2;
        _read >> cost;

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


void Write(vector<unsigned> const &costs) {
    for (unsigned i = 1; i < costs.size(); ++i) {
        if (costs[i] == MAXVAL) {
            _write << 0 << ' ';
        }
        else {
            _write << costs[i] << ' ';
        }
    }
}


void Dijkstra(vector<vector<Node>> const &nodes) {
    vector<unsigned> costs(nodes.size(), MAXVAL);
    priority_queue<unsigned, vector<unsigned>, greater<unsigned>> _queue;
    vector<bool> vis(nodes.size());

    unsigned node;
    unsigned i;

    _queue.push(0);
    costs[0] = 0;

    while (_queue.empty() == false) {
        node = _queue.top();
        _queue.pop();

        vis[node] = true;

        for (i = 0; i < nodes[node].size(); ++i) {
            if (vis[nodes[node][i].neighbour] == false)
            if (costs[node] + nodes[node][i].cost < costs[nodes[node][i].neighbour]) {
                costs[nodes[node][i].neighbour] = costs[node] + nodes[node][i].cost;
                _queue.push(nodes[node][i].neighbour);
            }
        }
    }

    Write(costs);
}


int main() {
    unsigned n;
    unsigned m;
    vector<vector<Node>> nodes;

    Read(n, m, nodes);

    Dijkstra(nodes);

    return 0;
}