#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define N 50005
struct Edge {
    int target;
    int weight;
};
struct Node {
    vector<Edge> adj;
}a[N];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int n, m, x, y, d;
vector<int> dijkstra() 
{
    vector<int> dist(n+1, INT_MAX);
    dist[1] = 0;
    pq.emplace(0, 1);
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();

        int di = top.first;
        int u = top.second;
        
        if (di > dist[u]) 
            continue;
        for (auto p : a[u].adj) {
            int v = p.target;
            int w = p.weight;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }

    return dist;
}
int main()
{
    fin >> n >> m;
    for (int i=1;i<=m;i++) {
        fin >> x >> y >> d;
        a[x].adj.push_back({y, d});
    }

    vector<int> result = dijkstra();
    for (int i=2;i<=n;i++) {
        fout << result[i] << ' ';
    }
    fout << '\n';
}