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


using namespace std;


char const in_file[] = "dijkstra.in";
char const out_file[] = "dijkstra.out";
unsigned const MAXVAL = (1LL << 31) - 1;


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


struct Node {
    unsigned index;
    unsigned cost;

    Node(unsigned const, unsigned const);
};


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


class Compare {
    public:
        bool operator()(Node const &first, Node const &second) {
            return first.cost > second.cost;
        }
};


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

    Read >> n;
    Read >> m;

    nodes.resize(n);

    unsigned node1;
    unsigned node2;
    unsigned 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<unsigned> &dist,
    unsigned const start_node
) {
    priority_queue<Node, vector<Node>, Compare> _queue;
    vector<bool> vis(nodes.size());
    unsigned node;
    unsigned neighbour;
    unsigned neighbour_dist;

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

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

        if (vis[node] == true) {
            continue;
        }

        vis[node] = true;

        for (unsigned i = 0; i < nodes[node].size(); ++i) {
            neighbour = nodes[node][i].index;

            if (vis[neighbour] == true) {
                continue;
            }

            neighbour_dist = dist[node] + nodes[node][i].cost;

            if (neighbour_dist < dist[neighbour]) {
                dist[neighbour] = neighbour_dist;
                _queue.push(nodes[node][i]);
            }
        }
    }
}


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

    Dijkstra(nodes, dist, 0);

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


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

    ReadInput(nodes);

    Solve(nodes);

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

    return 0;
}