#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;
}