#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pii;
const int inf = 1 << 30;

template<typename T>
class Graph {
public:
    // dfs

    void DFS(int v, vector<bool> &vis) {
        vis[v] = true;

        for (auto &x : m_ad[v]) {
            if (!vis[x]) {
                DFS(x, vis);
            }
        }
    }

    int components() {
        int compCount = 0;
        vector<bool> vis(m_n, false);

        for (int i = 1; i <= m_n; ++i) {
            if (!vis[i]) {
                ++compCount;
                DFS(i, vis);
            }
        }

        return compCount;
    }

    // bfs

    void minDist(int start, ostream &out) {
        vector<int> dist(m_n + 1, -1);
        queue<int> Q;
        int x;

        dist[start] = 0;
        Q.push(start);

        while (!Q.empty()) {
            x = Q.front(); Q.pop();

            for (auto &y : m_ad[x]) {
                if (dist[y] == -1) {
                    dist[y] = dist[x] + 1;
                    Q.push(y);
                }
            }
        }

        for (int i = 1; i <= m_n; ++i) {
            out << dist[i] << ' ';
        }
    }

    // sortare topologica

    void topologicalSort(int v, vector<bool> &vis, vector<int> &stack) {
        vis[v] = true;

        for (auto &x : m_ad[v]) {
            if (!vis[x]) {
                topologicalSort(x, vis, stack);
            }
        }

        stack.push_back(v);
    }

    void printTopoSorted(ostream &out) {
        vector<bool> vis(m_n + 1, false);
        vector<int> stack;

        for (int i = 1; i <= m_n; ++i) {
            if (!vis[i]) {
                topologicalSort(i, vis, stack);
            }
        }

        for (int i = stack.size() - 1; i >= 0; --i) {
            out << stack[i] << ' ';
        }
    }

    // ctc

    void tDFS(int v, vector<bool> &vis, int compCount, vector<vector<int>> &comp) {
        vis[v] = true;
        comp[compCount - 1].push_back(v);

        for (auto &x : m_tAd[v]) {
            if (!vis[x]) {
                tDFS(x, vis, compCount, comp);
            }
        }
    }

    void stronglyConnectedComponents(ostream &out) {
        vector<bool> vis1(m_n + 1, false);
        vector<bool> vis2(m_n + 1, false);
        vector<int> stack;
        int compCount = 0;
        vector<vector<int>> comp;

        for (int i = 1; i <= m_n; ++i) {
            if (!vis1[i]) {
                topologicalSort(i, vis1, stack);
            }
        }

        for (int i = stack.size() - 1; i >= 0; --i) {
            if (!vis2[stack[i]]) {
                ++compCount;
                comp.emplace_back();
                tDFS(stack[i], vis2, compCount, comp);
            }
        }

        out << compCount << '\n';

        for (int i = 0; i < compCount; ++i) {
            for (auto &x : comp[i]) {
                out << x << ' ';
            }

            out << '\n';
        }
    }

    // biconex

    void bccDFS(int v, int parent, vector<int> &disc, vector<int> &low,
                vector<int> &stack, vector<vector<int>> &comp) {
        static int time = 0;
        int children = 0;

        disc[v] = low[v] = ++time;

        for (auto &w : m_ad[v]) {
            if (w == parent) continue; // (w, v) e muchie de intoarcere

            if (!disc[w]) {
                ++children;
                stack.push_back(w);
                bccDFS(w, v, disc, low, stack, comp);
                low[v] = min(low[v], low[w]);

                if (low[w] >= disc[v]) {
                    comp.emplace_back();
                    stack.push_back(v);

                    while (!stack.empty() && stack.back() != w) {
                        comp[comp.size() - 1].push_back(stack.back());
                        stack.pop_back();
                    }

                    if (!stack.empty()) {
                        comp[comp.size() - 1].push_back(stack.back());
                        stack.pop_back();
                    }
                }
            } else if (w != parent) {
                low[v] = min(low[v], disc[w]);
            }
        }
    }

    void biconnectedComponents(ostream &out) {
        vector<int> disc(m_n + 1, 0);
        vector<int> low(m_n + 1, 0);
        vector<int> stack;
        vector<vector<int>> comp;

        bccDFS(1, 0, disc, low, stack, comp);

        out << comp.size() << '\n';

        for (auto &c : comp) {
            for (auto &v : c) {
                out << v << ' ';
            }

            out << '\n';
        }
    }

    // Havel Hakimi

    static bool eligible(vector<int> &v) {
        int s = 0;
        auto n = v.size();

        for (auto &x : v) {
            if (x > n - 1) {
                return false;
            }

            s += x;
        }

        return s % 2 == 0;
    }

    static string canBuildGraph(vector<int> &v) {
        if (!eligible(v)) {
            return "No";
        }

        sort(v.begin(), v.end(), greater<>());

        while (v[0]) {
            for (int i = 1; i <= v[0]; ++i) {
                if (v[i] == 0) {
                    return "No";
                }

                --v[i];
            }

            v.erase(v.begin());
            sort(v.begin(), v.end(), greater<>());
        }

        return "Yes";
    }

    // graf

    void findPaths(vector<vector<int>> &paths, vector<int> &path, vector<vector<int>> &parent, int current) {
        if (current == -1) {
            paths.push_back(path);
            return;
        }

        for (auto &p : parent[current]) {
            path.push_back(current);
            findPaths(paths, path, parent, p);
            path.pop_back();
        }
    }

    void BFS(vector<vector<int>> &parents, int start) {
        vector<int> dist(m_n + 1, inf);
        queue<int> Q;

        Q.push(start);
        parents[start] = {-1};
        dist[start] = 0;

        while (!Q.empty()) {
            int current = Q.front(); Q.pop();

            for (auto &x : m_ad[current]) {
                if (dist[current] + 1 < dist[x]) {
                    dist[x] = dist[current] + 1;
                    Q.push(x);

                    parents[x].clear();
                    parents[x].push_back(current);
                } else if (dist[x] == dist[current] + 1) {
                    parents[x].push_back(current);
                }
            }
        }
    }

    void optimalPaths(int start, int end, ostream &out) {
        vector<vector<int>> paths;
        vector<int> path;
        vector<vector<int>> parents(m_n + 1);

        BFS(parents, start);
        findPaths(paths, path, parents, end);

        vector<int> check(m_n + 1, 0);
        int pathCount = paths.size(), count = 0;

        for (auto &p : paths) {
            for (auto &v : p) {
                ++check[v];
            }
        }

        for (int i = 1; i <= m_n; ++i) {
            if (check[i] == pathCount) {
                ++count;
            }
        }

        out << count << '\n';

        for (int i = 1; i <= m_n; ++i) {
            if (check[i] == pathCount) {
                out << i << ' ';
            }
        }
    }

    // disjoint

    int find(int x, vector<int> &root) {
        int rx = x, aux;

        while (rx != root[rx]) {
            rx = root[rx];
        }

        while (x != root[x]) {
            aux = root[x];
            root[x] = rx;
            x = aux;
        }

        return rx;
    }

    void unite(int x, int y, vector<int> &root, vector<int> &size) {
        int rx = find(x, root);
        int ry = find(y, root);

        if (size[rx] > size[ry]) {
            root[ry] = rx;
            size[rx] += size[ry];
        } else {
            root[rx] = ry;
            size[ry] += size[rx];
        }
    }

    void disjoint(int n, vector<pair<int, pair<int, int>>> &ops, ostream &out) {
        vector<int> root(n + 1);
        vector<int> size(n + 1, 1);

        for (int i = 1; i <= n; ++i) {
            root[i] = i;
        }

        for (auto &op : ops) {
            if (op.first == 1) {
                unite(op.second.first, op.second.second, root, size);
            } else {
                if (find(op.second.first, root) == find(op.second.second, root)) {
                    out << "DA\n";
                } else {
                    out << "NU\n";
                }
            }
        }
    }

    // dijkstra

    void dijkstra(ostream &out) {
        vector<int> dist(m_n + 1, inf);
        vector<bool>inHeap(m_n + 1, false);
        priority_queue<pii, vector<pii>, greater<pii>> heap;

        dist[1] = 0;
        heap.push({1, 0});

        while (!heap.empty()) {
            int current = heap.top().first;
            heap.pop();

            if (!inHeap[current]) {
                inHeap[current] = true;

                for (auto &w : m_ad[current]) {
                    if (dist[current] + w.second < dist[w.first]) {
                        dist[w.first] = dist[current] + w.second;
                        heap.push({w.first, dist[w.first]});
                    }
                }
            }
        }

        for (int i = 2; i <= m_n; ++i) {
            if (dist[i] != inf) {
                out << dist[i] << ' ';
            } else {
                out << "0 ";
            }
        }
    }

    // constructori

    Graph() : m_n(0), m_ad(), m_tAd() {}

    Graph(int n, vector<vector<T>> &ad) :
            m_n(n), m_ad(ad), m_tAd() {}

    Graph(int n, vector<vector<T>> &ad, vector<vector<T>> &tAd) :
            m_n(n), m_ad(ad), m_tAd(tAd) {}

private:
    int m_n;
    vector<vector<T>> m_ad;
    vector<vector<T>> m_tAd;
};

int main() {
    int n, m, x, y, cost;

    fin >> n >> m;

    vector<vector<pair<int, int>>> ad(n + 1);

    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> cost;
        ad[x].push_back({y, cost});
    }

    Graph<pair<int, int>> G(n, ad);
    G.dijkstra(fout);

    return 0;
}