#include <queue>
#include <vector>
#include <fstream>

#define DMAX 50010

using std::vector;
using std::priority_queue;

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

struct Arc {
    int node;
    int cost;
};

inline bool operator<(Arc x, Arc y) {
    return x.cost > y.cost;
}

int n, m;
vector<Arc> ad[DMAX];

int dp[DMAX];
bool onPQ[DMAX];
priority_queue< int, vector<int> > pq;

int main() {
    int a, b, c;

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        ad[a].push_back({b, c});
    }

    pq.push(1);
    onPQ[1] = true;

    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        onPQ[node] = false;

        for (Arc arc : ad[node])
            if (!dp[arc.node] || dp[node] + arc.cost < dp[arc.node]) {
                dp[arc.node] = dp[node] + arc.cost;
                if (!onPQ[arc.node]) {
                    pq.push(arc.node);
                    onPQ[arc.node] = true;
                }
            }
    }

    for (int i = 2; i <= n; i++)
        fout << dp[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}