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

#define INF 0x3f3f3f3f


std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");


class Graph {
private:
    int V;
    std::vector<std::vector<std::pair<int, int>>>adj;
    std::vector<int>cost_min;
public:
    Graph(int n) {
        V = n;
        adj.resize(V+1);
        cost_min.resize(V+1, INF);
    }

    void addEdge(int x, int y, int z) {
        adj[x].push_back({y, z});
    }

    void dijsktra(int src) {
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

        cost_min[src] = 0;
        pq.emplace(0, src);

        while(!pq.empty()) {
            std::pair<int, int> c = pq.top();
            pq.pop();

            int d = c.first;
            int u = c.second;

            if(cost_min[u] < d) continue;

            for(const std::pair<int, int>& p : adj[u]) {
                int v = p.first;
                int w = p.second;

                if(cost_min[v] > cost_min[u] + w) {
                    cost_min[v] = cost_min[u] + w;
                    pq.emplace(cost_min[v], v);
                }
            }
        }

        for(int i = 2;i<=V;++i) {
            int print = (cost_min[i] == INF) ? 0 : cost_min[i];
            fout << print << " ";
        }
    }
};




int main(void) {
    int n, m, x, y, z;

    fin >> n >> m;
    Graph g(n);

    for(int i=1;i<=m;++i) {
        fin >> x >> y >> z;
        g.addEdge(x, y, z);
    }

    g.dijsktra(1);

    return 0;
}