#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

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

int INF = 1 << 30;

class graf_orientat{
    int nrNoduri;
    vector<vector<pair<int, int>>> muchii;

public:
    void citire(){
        int nrMuchii;
        in >> this->nrNoduri >> nrMuchii;
        this->muchii.resize(nrMuchii + 1);
        for(int i = 0; i < nrMuchii; i++){
            int from, to, cost;
            in >> from >> to >> cost;
            muchii[from].push_back(make_pair(to, cost));
        }
    }

    vector<int> dijkstra(int nod_start){
        vector<int> dist(nrNoduri + 1);
        priority_queue<pair<int, int>> coada; /// coada contine perechi de forma (cost, to)
        vector<bool> vizitat(nrNoduri + 1);

        for(int i = 1; i <= nrNoduri; i++){
            dist[i] = INF;
            vizitat[i] = false;
        }
        dist[nod_start] = 0;

        coada.push({0, nod_start});

        while(!coada.empty()){
            pair<int, int> nod_curent = coada.top();
            /// fac costul la loc pozitiv pentru a putea calcula distanta totala
            nod_curent.first = -nod_curent.first;
            coada.pop();

            if(vizitat[nod_curent.second])
                continue;

            vizitat[nod_curent.second] = true;
            for(auto i: muchii[nod_curent.second]){
                /// formez fiecare vecin de forma           {cost,                                      to}
                pair<int, int> vecin = make_pair(i.second, i.first);
                if(dist[nod_curent.second] + vecin.first < dist[vecin.second] && !vizitat[vecin.second]){
                    dist[vecin.second] = dist[nod_curent.second] + vecin.first;

                    /// pastrez costul negativ in coada pentru a fi luat prima data muchia cu costul cel mai mic
                    coada.push({-vecin.first, vecin.second});
                }
            }
        }

        dist[nod_start] = -1;
        /*for(auto i: dist){
            if(i != -1){
                cout << i << " ";
            }
        }*/
        return dist;
    }

    void afisare(){
        cout << nrNoduri << endl;
        for(int i = 0; i < muchii.size(); i++)
            for(int j = 0; j < muchii[i].size(); j++)
                cout << i << " " << muchii[i][j].first << " " << muchii[i][j].second << endl;
    }
};

int main()
{
    graf_orientat g;
    g.citire();
    //g.afisare();
    vector<int> res = g.dijkstra(1);

    for(int i = 2; i < res.size(); i++){
        cout << res[i] << " ";
    }
    return 0;
}