#include <bits/stdc++.h>
#define nmax 50005

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

int n, m, x, y, C, D[nmax];
bool viz[nmax];
vector < pair < int , int > > G[nmax];
const int inf = 1072500000;

struct fcmp {
    bool operator() (int x, int y) {
        return D[x] > D[y];
    }
};

priority_queue < int, vector < int >, fcmp > Q;

void Read () {
    fin >> n >> m;
    while (m --) {
        fin >> x >> y >> C;
        G[x].push_back ({y, C});
    }
}

void Dijkstra (int start) {
    memset (D, inf, sizeof(D));
    D[start] = 0;
    Q.push (start);
    viz[start] = true;
    while (!Q.empty()) {
        int nod = Q.top();
        Q.pop();
        viz[nod] = false;
        for (size_t i = 0; i < G[nod].size(); ++i) {
            int vecin = G[nod][i].first;
            int cost = G[nod][i].second;
            if (D[nod] + cost < D[vecin]) {
                D[vecin] = D[nod] + cost;
                if (!viz[vecin]) {
                    Q.push (vecin);
                    viz[vecin] = true;
                }
            }
        }
    }
}

void Print () {
    for (int i = 2; i <= n; ++i) if (D[i] != inf) fout << D[i] << " ";
                                    else fout << "0 ";
}

int main() {
    Read ();
    Dijkstra (1);
    Print ();
    return 0;
}