#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <utility>
#include <set>
#define mp make_pair
#define Dp pair<int,int>

using namespace std;

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

const int f_mare = 2e9;
int n, m, i, j, x, y, c;
int d[50005];
vector<Dp > ls[50005];
set <Dp > H;

int main() {
    f >> n >> m;

    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;
        ls[x].push_back(mp(y, c));
    }
    for(i = 2; i<=n;d[i] = f_mare, i++);
    d[1] = 0;
    H.insert(mp(1, 0) );
    int cc;
    while (!H.empty()) {
        x = H.begin() -> first;
        cc = H.begin() -> second;
        H.erase(H.begin());

        for (i = 0; i < ls[x].size(); i++) {
            y = ls[x][i].first;
            c = ls[x][i].second;
            if (d[x]+c < d[y]) {
                if (d[y] < f_mare)
                    H.erase(H.find(mp(y, d[y])));
                d[y] = d[x]+c;
                H.insert(mp(y, d[y]));
            }
        }
    }

    for (i = 2; i <= n; i++)
        g << d[i]%f_mare << ' ';

    return 0;
}