#include <stdio.h>
#include <queue>
#include <vector>
#define nmax 50001
#define inf 1<<30

using namespace std;

vector < pair <int, int> > G[nmax];
queue <int> q;
int cmin[nmax];

int main() {
    int N, M, i, x, y, z, m;
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);
    scanf ("%d %d", &N, &M);
    for (i = 1; i <= M; ++i) {
        scanf ("%d %d %d", &x, &y, &z);
        G[x].push_back (make_pair(y,z));
    }
    for (i = 2; i <= N; ++i)
        cmin[i] = inf;
    cmin[1] = 0;
    q.push(1);
    while (!q.empty()) {
        x = q.front();
        q.pop();
        m = G[x].size();
        for (i = 0; i < m; ++i) {
            y = G[x][i].first;
            z = G[x][i].second;
            if (cmin[y] > cmin[x] + z)
                cmin[y] = cmin[x] + z, q.push(y);
        }
    }
    for (i = 2; i <= N; ++i)
        printf ("%d ", cmin[i]);
    return 0;
}