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

#define NMAX 50010

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

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

struct Arc {
    int node, cost;
    Arc(int node, int cost) {
        this->node = node;
        this->cost = cost;
    }
};

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

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

int dp[NMAX];
bool inPQ[NMAX];
priority_queue<Arc> pq;

int main() {
    int x, y, z;

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> z;
        ad[x].push_back(Arc(y, z));
    }

    for (int i = 2; i <= n; i++)
        dp[i] = INT_MAX;

    pq.push(Arc(1, 0));
    inPQ[1] = true;

    while (!pq.empty()) {
        int node = pq.top().node;
        pq.pop();

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

    for (int i = 2; i <= n; i++)
        if (dp[i] != INT_MAX)
            fout << dp[i] << ' ';
        else
            fout << "0 ";
    fout << '\n';

    fout.close();
    return 0;
}