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];

class ComparVf{
    public:
    bool operator() (const int& x, const int& y) {
       return cmin[x] > cmin[y];
    }
};
priority_queue<int, vector<int>, ComparVf> 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(p);

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

    while (!H.empty()) {

        vfmin = H.top();
        H.pop();
        if (cmin[vfmin] == INF) break;

        for (int i = 0; i<G[vfmin].size(); i++) {
            int x = G[vfmin][i].first, c = G[vfmin][i].second;
            if (cmin[x] > cmin[vfmin] + c) {
                cmin[x] = cmin[vfmin] + c;
                H.push(x);
            }
        }
    }
}

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