#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int MAXN = 50001;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> g[MAXN];
int dist[MAXN];
bool seen[MAXN];

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        g[a].push_back(make_pair(b, c));
    }

    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 1));

    while (!pq.empty()) {
        int d = pq.top().first;
        int x = pq.top().second;
        pq.pop();
        if (seen[x]) continue;
        seen[x] = true;

        for (int i = 0; i < (int)g[x].size(); i++) {
            int y = g[x][i].first;
            int c = g[x][i].second;
            if (dist[y] > d + c) {
                dist[y] = d + c;
                pq.push(make_pair(dist[y], y));
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        printf("%d ", dist[i] == INF ? 0 : dist[i]);
    }
    return 0;
}