#include <iostream>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

const int INF = INT_MAX;

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

struct Muchie{
    int next, w;
};

vector<int> dijsktra(int N, vector<vector<Muchie>>& adj, int start){
    vector<int> dist(N + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while(!pq.empty()){
        int nod = pq.top().second, k = pq.top().first;
        pq.pop();
        if(dist[nod] > k) continue;
        for(auto& muchie : adj[nod]){
            int kNext = dist[nod] + muchie.w;
            if(kNext < dist[muchie.next]){
                dist[muchie.next] = kNext;
                pq.push({kNext, muchie.next});
            }
        }
    }
    return dist;
}

int main()
{
    int N, M;
    in >> N >> M;

    vector<vector<Muchie>> adj(N + 1);

    for(int i = 0; i < M; i++){
        int a, b, c;
        in >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    vector<int> dist = dijsktra(N, adj, 1);

    for(int i = 2; i <= N; i++){
        out << dist[i] << " ";
    }
    return 0;
}