#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

class graf {

protected:
    int noduri, muchii;
    vector < vector < int >> adiacenta;

public:
    // Constructor cu matrice de adiacenta data
    graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii): adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};

    // Constructor fara matrice de adiacenta, se cu initalizeaza una goala
    graf(int noduri, int muchii): adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};

    vector < int > bfs(int);
    int dfs();

};

class graf_neorientat : public graf{
private:
    void dfsbiconex(int, vector < int >&, vector < int >&, stack < pair < int, int >>&, int&, vector < string >&);
    void dfsCriticalConnections(int tata, vector < int >&, vector < int >&, int&, vector < vector < int >>&, vector < int >&);

public:
    graf_neorientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
    graf_neorientat(int noduri, int muchii): graf(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_neorientat&);

    vector < string > biconex();

    vector < vector < int >> criticalConnections();
};

class graf_neorientat_ponderat : public graf_neorientat {
    // Matrice de adianceta care contine si costurile
    vector< vector< pair< int, int >>> adiacentap;
public:
    graf_neorientat_ponderat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf_neorientat(listaAdiacenta, noduri, muchii) {};
    graf_neorientat_ponderat(int noduri, int muchii): adiacentap(noduri+1), graf_neorientat(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_neorientat_ponderat&);

    unordered_map<int, int> dijkstra();

};

istream& operator>>(istream& in, graf_neorientat_ponderat& g) {
    for (int i = 0; i < g.muchii; i++) {
        int aux1, aux2, aux3;
        in >> aux1 >> aux2 >> aux3;
        g.adiacentap[aux1].push_back(make_pair(aux2, aux3));
    }
    return in;
}

unordered_map<int, int> graf_neorientat_ponderat :: dijkstra() {

    unordered_map<int, int> m;
    priority_queue<vector<int>> p;

    m[1] = 0;
    p.push({0, 1});
    while(!p.empty()){
        vector<int> muchie = p.top();
        p.pop();
        for(auto i : adiacentap[muchie[1]]){
            int nod = i.first, cost = i.second;
            if(m.find(nod) == m.end() || m[nod] > m[muchie[1]] + cost){
                //cout<<i.first<<" "<<m[nod]<<endl;
                m[nod] = m[muchie[1]] + cost;
                p.push({-(m[nod]), nod});
            }
        }
    }
    return m;

}

void dijkstraDriver() {
    // https://infoarena.ro/problema/dijkstra
    // Citire
    ifstream in ("dijkstra.in");
    ofstream out("dijkstra.out");

    int n, m;
    in >> n >> m;

    graf_neorientat_ponderat x(n, m);
    in>>x;
    unordered_map<int, int> v = x.dijkstra();
    for(int i=2; i<=n; i++){
        if(v.find(i)==v.end()){
            out<<"0 ";
        }
        else{
            out<<v[i]<<" ";
        }
    }

}

int main() {
    // Se apeleaza functia corespunzatoare problemei
    dijkstraDriver();
    return 0;
}