#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 50005;
const int INF = 2000000000;
struct Muchie {
    int x, cost;
};
vector <Muchie> vec[NMAX];
int cost[NMAX];
struct Dijkstra {
    int x, cost;
    bool operator < (const Dijkstra &other) const {
        if(this->cost == other.cost) {
            return this->x > other.x;
        }
        return this->cost > other.cost;
    }
};
priority_queue <Dijkstra> pq;

int main() {
    int n, m;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        vec[x].push_back({y, cost});
    }
    for(int i = 1; i <= n; i++) {
        cost[i] = INF;
    }
    cost[1] = 0;
    pq.push({1, 0});
    while(!pq.empty()) {
        auto u = pq.top();
        pq.pop();
        if(cost[u.x] == u.cost) {
            for(int i = 0; i < vec[u.x].size(); i++) {
                int v = vec[u.x][i].x;
                int nc = vec[u.x][i].cost;
                if(cost[v] > nc + u.cost) {
                    cost[v] = nc + u.cost;
                    pq.push({v, cost[v]});
                }
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        if(cost[i] == INF) {
            cost[i] = 0;
        }
        printf("%d ", cost[i]);
    }
    printf("\n");
    return 0;
}