#include<iostream>

#include<fstream>

#include<vector>

#include<set>

#define MAX_VERTICES 50000

#define oo 0x3f3f3f3f

using namespace std;



class Graph {

private:

    int V;

    int E;

    vector<pair<int, int>> g[MAX_VERTICES + 1];

public:

    void readGraph() {

        ifstream fin("dijkstra.in");

        int x, y, c;

        fin >> V >> E;

        for(int i = 0; i < E; ++i) {

            fin >> x >> y >> c;

            g[x].push_back(make_pair(y, c));

        }

        fin.close();

    }



    void Dijkstra(int startNode) {

        ofstream fout("dijkstra.out");

        vector<int>dist(MAX_VERTICES + 1, oo);

        set<pair<int, int>>s;

        int node;

        dist[startNode] = 0;

        s.insert(make_pair(0, startNode));

        while(!s.empty()) {

            node = s.begin()->second;

            s.erase(s.begin());

            for(auto i : g[node]) {

                if(dist[i.first] > dist[node] + i.second) {

                    if(dist[i.first] != oo)

                        s.erase(s.find(make_pair(dist[i.first], i.first)));

                    dist[i.first] = dist[node] + i.second;

                    s.insert(make_pair(dist[i.first], i.first));

                }

            }

        }

        for(int i = 2; i <= V; ++i)

            if(dist[i] == oo)

                fout << "0 ";

            else fout << dist[i] << " ";

        fout << "\n";

        fout.close();

    }

};



int main() {

    Graph G;

    G.readGraph();

    G.Dijkstra(1);

    return 0;

}