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

using namespace std;

// ALGORITMUL LUI DIJKSTRA
// Complexitate O(N * logN + M * logN) = O((N+M)logN)

//ifstream cin ("input");ofstream cout ("output");
ifstream cin ("dijkstra.in");ofstream cout ("dijkstra.out");

const int inf = 1e9;

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> q; // elementul minim
vector<int> dist;
vector<vector<pair<int,int>>> gr;

int main() {

    int n , m;
    cin>>n>>m;

    dist.resize(n+1);
    gr.resize(n+1);

    for (int i=2; i<=n; i++){
        dist[i] = inf;
    }

    for (int i=1; i<=m; i++){
        int a , b , val;
        cin>>a>>b>>val;
        gr[a].push_back({b , val});
    }

    q.push({0, 1}); // initial eu il am doar pe 1 cu cost 0

    while (!q.empty()){
        pair<int,int> now = q.top(); // iau nodul cu valoarea cea mai mica
        q.pop(); // scos nod din priority queue - O(logN)

        int distCurenta = now.first;
        int nod = now.second;

        if (distCurenta != dist[nod]){ // verific sa nu se fi schimbat valoarea
            continue;
        }
        for (auto &x : gr[nod]){
            if (dist[x.first] > distCurenta + x.second){ // daca un vecin poate fi actualizat - fac asta si il bag in priority queue
                dist[x.first] = distCurenta + x.second;
                q.push({dist[x.first], x.first}); // adaugat nod in priority queue - O(logN)
            }
        }
    }

    for (int i=2; i<=n; i++){
        if (dist[i] == inf){
            cout<<0<<" ";
        }
        else{
            cout<<dist[i]<<" ";
        }
    }

    return 0;
}