#include <bits/stdc++.h>
using namespace std;
long long mx =1000001;

string __fname = "dijkstra";  
ifstream in(__fname + ".in"); 
ofstream out (__fname + ".out"); 
#define cin in 
#define cout out
int main(){
    int n, m;
    cin >> n >> m; // citim numarul de noduri(n), si numarul de muchii(m).
    int sursa = 1; // nodul sursa.
    vector<vector<pair<int, int>>> adj(n + 1); // cream lista de adiacenta a acestui graf
    for(int i = 0; i < m; i++){
        int x, y, z; // x - nodul de unde se porneste muchia, y - nodul final, z - costul.
        cin >> x >> y >> z;
        adj[x].push_back({y, z}); // introducem in lista de adiacenta valorile.
    }
    vector<int> d(n + 1, mx); // vectorul pentru a stoca valorile a celui mai scurt drum.
    vector<int> p(n + 1, -1); // vectorul pentru a stoca drumul parcurs
    d[sursa] = 0;
    set<pair<int, int>> s; // un set cu ajutorul caruia vom parcurge fiecare muchie.
    s.insert({sursa, 0});// introducem in set valoarea primului element adica a sursei cu costul = 0.
    while(!s.empty()){ 
        int u = s.begin()->first; // luam datele primului nod din set
        int v = s.begin()->second;
        s.erase(s.begin());// il scoatem din set
        for(int i = 0; i < (int)adj[u].size(); i++){//parcurgem fiecare nod in care putem ajunge din nodul curent(u)
            if(d[adj[u][i].first] > v + adj[u][i].second){//vedem daca putem imbunatati costul drumului.
                d[adj[u][i].first] = v + adj[u][i].second;
                s.insert({adj[u][i].first, d[adj[u][i].first]});//schimbam costul drumul si il introducem in set pe nodul imbunatatit.
                p[adj[u][i].first] = u;//scriem in vectorul p nodul din care provine
            }
        }
    }
    for(int i = 2; i <= n; i++){// scriem toate costurile minime din graf.
        // if(d[i] == mx){
        //     // cout << i << ": nu exista drum catre acest nod\n";
        //     continue;
        // }
        // cout << i << ": "<< 
        if(d[i] == mx){
            cout << 0 << ' ';
        }
        else cout << d[i] << ' ';
    }
    // for(int i = 0; i < n; i++){// scriem drumurile alese pentru fiecare nod.
    //     vector<int> drum;
    //     if(p[i] == -1 && i != sursa){
    //         cout << i << ": nu exista drum catre acest nod\n";
    //         continue;
    //     }
    //     for(int j = i; j != sursa; j = p[j]){
    //         drum.push_back(j);
    //     }
    //     drum.push_back(sursa);
    //     reverse(drum.begin(), drum.end());
        
    //     for(int j = 0; j < (int)drum.size();j++){
    //         if(j == 0 ){
    //             cout << drum[j];
    //             continue;
    //         }
    //         cout << " -> " << drum[j];
    //     }
    //     cout << ".\n";
    // }
}