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

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int MAXN = 50005;

int n, m;

vector<pair<int,int>> adj[MAXN];

vector<long long> Dijkstra(int start, vector<int> &tata) {

    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> q;

    vector<long long> d(n+1, 1e18);
    d[start] = 0;

    q.push({0, start});

    while (!q.empty()) {
        auto top = q.top();
        q.pop();

        long long uDist = top.first;
        int u = top.second;

        if (uDist > d[u]) continue;

        for (auto vecin : adj[u]) {
            int v = vecin.first;
            int cost = vecin.second;

            if (d[u] + cost < d[v]) {
                d[v] = d[u] + cost;
                tata[v] = u;
                q.push({d[v], v});
            }
        }
    }

    return d;
}

int main() {
    f>>n>>m;
    for (int i=1;i<=m;i++) {
        int nod1, nod2, cost;
        f>>nod1>>nod2>>cost;
        adj[nod1].push_back({nod2, cost});
    }

    vector<int> tata(n+1, 0);
    vector<long long> dist = Dijkstra(1, tata);

    for (int i = 2; i <= n; i++) {
        if (dist[i]>=1e18) g << 0 << " ";
        else g<<dist[i]<<" ";
    }
    g<<"\n";
    return 0;
}