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

using namespace std;


struct Node {
    unsigned node;
    unsigned cost;

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


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


class Compare {
    public:
        bool operator()(Node const &first, Node const &second) {
            return first.cost > second.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 &dist) {
    for (unsigned i = 1; i < dist.size(); ++i) {
        if (dist[i] == MAXVAL) {
            _write << 0 << ' ';
        }
        else {
            _write << dist[i] << ' ';
        }
    }
}


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

    unsigned node;
    unsigned i;

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

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

        vis[node] = true;

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

    Write(dist);
}


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

    Read(n, m, nodes);

    Dijkstra(nodes);

    return 0;
}