using namespace std;
#include<iostream>
#include<fstream>
#include <queue>

#define NMAX 50002
#define INF 1e9 + 2

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

int n, p = 1;
vector<pair<int,int>> G[NMAX];
int cmin[NMAX];
bool uz[NMAX];

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

void citire();
void dijkstra();
void afisare();

int main() {

    citire();
    dijkstra();
    afisare();

    return 0;
}

void citire() {
    int i,j,c,m;
    pair<int,int> vf;
    fin >> n >> m;
    for (int k = 0; k<m; k++) {
        fin >> i >> j >> c;
        vf.first = j, vf.second = c;
        G[i].push_back(vf);
    }

}

void dijkstra() {
    ///initializare
    int minim, vfmin;
    H.push(make_pair(0,p));

    for (int i = 1; i<=n; i++) {
        cmin[i] = INF;
    }
    cmin[p] = 0;

    while (!H.empty()) {

        vfmin = H.top().second;
        H.pop();

        if (cmin[vfmin] == INF) break;
        if (uz[vfmin]) continue;

        uz[vfmin] = 1;
        for (int i = 0; i<G[vfmin].size(); i++) {

            int x = G[vfmin][i].first, c = G[vfmin][i].second;
            if (uz[x]) continue;
            if (cmin[x] > cmin[vfmin] + c) {
                cmin[x] = cmin[vfmin] + c;
                H.push(make_pair(cmin[x],x));
            }
        }
    }
}

void afisare() {
    for (int i = 2; i<=n; i++) {
        if (cmin[i] == INF) {
            cmin[i] = 0;
        }
        fout << cmin[i] << " ";
    }
}