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

using namespace std;

const int nmax = 50000;
const int inf = 2000000000;

struct Muchie {
    int to, cost;
};

struct Nod {
    int nod, cost;
    bool operator> (Nod other) const {
        return (cost > other.cost);
    }
};

vector<Muchie> g[1 + nmax];
priority_queue<Nod, vector<Nod>, greater<Nod> > pq;
int sol[1 + nmax];

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

    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++ i) {
        int from, to, c;
        scanf("%d%d%d", &from, &to, &c);
        g[from].push_back({to, c});
    }

    fill(sol + 1, sol + n + 1, inf);
    pq.push({1, 0});
    sol[1] = 0;

    while(!pq.empty()) {
        int from = pq.top().nod;

        for(int k = 0; k < g[from].size(); ++ k) {
            Muchie e = g[from][k];
            if(sol[e.to] > sol[from] + e.cost) {
                pq.push({e.to, sol[from] + e.cost});
                sol[e.to] = sol[from] + e.cost;
            }
        }

        pq.pop();
    }

    for(int i = 2; i <= n; ++ i) {
        printf("%d ", sol[i]);
    }

    return 0;
}