#include <bits/stdc++.h>
using namespace std;

const int kNmax = 50005;
const int kInf = 0x3f3f3f3f;

class Task {
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    int n;
    int m;
    int source;
    vector<pair<int, int> > graf[kNmax];

    struct minHeap {
        bool operator() (pair<int, int> x, pair<int, int> y) {
            return y.second < x.second;
        }
    };

    priority_queue <pair<int, int>, vector <pair<int, int>>, minHeap> heap;
    int cost[kNmax];


    void read_input() {
        ifstream fin("in");
        fin >> n >> m;
        source = 1;
        for (int i = 1, x, y, w; i <= m; i++) {
            fin >> x >> y >> w;
            graf[x].push_back(make_pair(y, w));
        }
        fin.close();
    }

    void init() {
        for (int u = 1; u <= n; u++) {
            cost[u] = kInf;
        }
    }

    void dijkstra (int start) {
        int i;
     
        cost[start] = 1;
        heap.push(make_pair(start, cost[start]));
        while (!heap.empty()) {
            pair<int, int> act = heap.top();
            heap.pop();
            if (act.second == cost[act.first]) {
                for (i = 0; i != graf[act.first].size(); i++) {
                    if (cost[act.first] + graf[act.first][i].second < cost[graf[act.first][i].first]) {
                        cost[graf[act.first][i].first] = cost[act.first] + graf[act.first][i].second;
                        heap.push(make_pair(graf[act.first][i].first, cost[graf[act.first][i].first]));
                    }
                }
            }
        }
    }

    vector<int> get_result() {
        /*
        TODO: Gasiti distantele minime de la nodul source la celelalte noduri
        folosind Dijkstra pe graful orientat cu n noduri, m arce stocat in adj.
            d[node] = costul minim / lungimea minima a unui drum de la source la nodul
        node;
            d[source] = 0;
            d[node] = -1, daca nu se poate ajunge de la source la node.

        Atentie:
        O muchie este tinuta ca o pereche (nod adiacent, cost muchie):
            adj[x][i].first = nodul adiacent lui x,
            adj[x][i].second = costul.
        */
        vector<int> d(n + 1, 0);

        init();
        dijkstra(source);

        return d;
    }

    void print_output(vector<int> result) {
        ofstream fout("out");
        for (int i = 2; i <= n; i++) {
            if (cost[i] == kInf) {
                fout << 0 << " ";
            } else {
                fout << cost[i] - 1 << " ";
            }
        }
        fout << "\n";
        fout.close();
    }
};

// Please always keep this simple main function!
int main() {
    // Allocate a Task object on heap in order to be able to 
    // declare huge static-allocated data structures inside the class.
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}