#include <cstdio>
#include <vector>
#define f_mare 1000000005
#include <set>

using namespace std;

int dist[50005],n,m,i,j,x,y,c,l;
vector<int> ls[50005], lc[50005];
set <pair <int, int> >dij;
set <pair<int,int> >::iterator w;

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d\n", &x, &y, &c);
        ls[x].push_back(y);
        lc[x].push_back(c);
    }
    for (i = 2; i <= n; i++)
        dist[i] = f_mare;
    dij.insert(make_pair(0,1));
    while (dij.empty() == 0) {
        x = dij.begin() ->second;
        c = dij.begin() ->first;
        dij.erase(dij.begin());
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            y = ls[x][i];
            if (dist[x] + lc[x][i] < dist[y]) {
                w = dij.find(make_pair(dist[y], y)); // scoate costul vechi al nodului y
                if (w != dij.end())
                    dij.erase(w);
                dist[y] = dist[x] + lc[x][i];              // dupa ce actualizeaza costul,
                dij.insert(make_pair(dist[y], y));   // pune costul nou in set
            }
        }
    }
    for (i = 2; i <= n; i++)
        printf("%d ", (dist[i] == f_mare?0:dist[i]));
    return 0;
}