#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

const int INF = 20001;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


class Graph {
private:
    int _n, _m;
    vector<vector<int>> _list;
    vector<vector<pair<int, int> >> _list2;

    int viz[100001] = {0};

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void addEdges();

    void addEdges_Oriented();

    void add();

    vector<int> Dijkstra(int s);
};

void Graph::addEdges() {
    int x, y, i;
    for (i = 0; i < _m; ++i) {
        f >> x >> y;
        _list[x].push_back(y);
        _list[y].push_back(x);
    }
}

void Graph::addEdges_Oriented() {
    int x, y, i;
    for (i = 0; i < _m; ++i) {
        f >> x >> y;
        _list[x].push_back(y);
    }
}

void Graph::add() {
    int x, y, c;
    _list2.resize(_n + 1);

    for (int i = 0; i < _m; ++i) {
        f >> x >> y >> c;
        _list2[x].push_back(make_pair(y, c));
    }
}

//complexitate O(m*log n)
vector<int> Graph::Dijkstra(int start) {
    vector<int> dist(_n, INF);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    dist[start] = 0;
    q.push(make_pair(0, start));

    while (!q.empty()) {
        int currentNode = q.top().second;
        q.pop();

        if (viz[currentNode] == 0) {
            viz[currentNode] = 1;

            for (int i = 0; i < _list2[currentNode].size(); ++i) {
                int neighbour = _list2[currentNode][i].first;
                int cost = _list2[currentNode][i].second;

                if (dist[neighbour] > dist[currentNode] + cost) {
                    dist[neighbour] = dist[currentNode] + cost;
                    q.push(make_pair(dist[neighbour], neighbour));
                }
            }
        }

    }
    return dist;
}


int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.add();

    vector<int> answer = gr.Dijkstra(1);

    for (int i = 2; i <= n; ++i)
        if (answer[i] != INF)
            g << answer[i] << ' ';
        else g << 0 << ' ';

    f.close();
    g.close();
    return 0;
}