#include <bits/stdc++.h>

using namespace std;

const int INF = INT_MAX;

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

using namespace std;

struct Muchie{
    int nod, w;
    friend bool operator < (const Muchie& a, const Muchie& b){
        return a.w > b.w;
    }
};

void dijkstra(vector<vector<Muchie>>& adj, array<int, 50001> dist, int N){
    priority_queue<Muchie> pq;
    dist[1] = 0;
    for(const auto& k : adj[1]){
        pq.push({k.nod, k.w});
    }
    while(!pq.empty()){
        const Muchie k = pq.top();
        pq.pop();
        if(!dist[k.nod]){
            dist[k.nod] = k.w;
            for(const auto& t : adj[k.nod]){
                if(!dist[t.nod])
                    pq.push({t.nod, t.w + k.w});
            }
        }
    }
    for(int i = 2; i <= N; i++){
        if(dist[i] == INF)
            out << "0";
        else
            out << dist[i] << " ";
    }
}

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

    vector<vector<Muchie>> adj(N + 1);
    array<int, 50001> dist;

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

    dijkstra(adj, dist, N);
    return 0;
}