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

using namespace std;

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

const int f_mare = 1e9;
int n, m, i, j, x, y, c, l, t;
set <PR> cd;
vector <PR> ls[50005];
int dist[50005];

int main() {
    f >> n >> m;
    for (i = 2; i <= n; i++)
        dist[i] = f_mare;
    while (m--) {
        f >> x >> y >> c;
        ls[x].push_back(mp(c,y));
    }
    l = ls[1].size();
    cd.insert(mp(0,1));
    while (cd.empty() == 0) {
        t = cd.begin() -> first;
        x = cd.begin() -> second;
        cd.erase(cd.begin());
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            y = ls[x][i].second;
            c = ls[x][i].first;
            if (dist[x]+c < dist[y]) {
                if (dist[y] != f_mare)
                    cd.erase(cd.find(mp(dist[y], y)));
                dist[y] = dist[x]+c;
                cd.insert(mp(dist[y],y));
            }
        }
    }
    for (i = 2; i <= n; i++)
        g << (dist[i]==f_mare?0:dist[i]) << ' ';
    return 0;
}