#include <vector>
#include <fstream>

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

const int INF = 1e9 + 7;

class MinHeap {
    std::vector<std::pair<int, int>> v;

public:
    MinHeap() {}

    void insertKey(std::pair<int, int> key) {
        v.push_back(key);
        int i = v.size() - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (v[i].first < v[parent].first) {
                std::swap(v[i], v[parent]);
                i = parent;
            } else {
                break;
            }
        }
    }

    void MinHeapify(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;

        if (left < v.size() && v[left].first < v[smallest].first) {
            smallest = left;
        }
        if (right < v.size() && v[right].first < v[smallest].first) {
            smallest = right;
        }
        if (smallest != i) {
            std::swap(v[i], v[smallest]);
            MinHeapify(smallest);
        }
    }

    std::pair<int, int> pop() {
        if (v.empty()) return {INF, -1};

        if (v.size() == 1) {
            std::pair<int, int> root = v.back();
            v.clear();
            return root;
        }

        std::pair<int, int> root = v[0];
        v[0] = v[v.size() - 1];
        v.pop_back();
        MinHeapify(0);

        return root;
    }

    bool empty() {
        return v.empty();
    }
};

int main() {

    int N, M;
    if (!(fin >> N >> M)) return 0;

    std::vector<std::vector<std::pair<int, int>>> adj(N + 1);

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    std::vector<int> dist(N + 1, INF);
    dist[1] = 0;

    MinHeap pq;
    pq.insertKey({0, 1});

    while (!pq.empty()) {
        std::pair<int, int> current = pq.pop();
        int d = current.first;
        int u = current.second;

        if (d > dist[u]) {
            continue;
        }

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.insertKey({dist[v], v});
            }
        }
    }

    for (int i = 2; i <= N; ++i) {
        if (dist[i] == INF) {
            fout << 0 << " ";
        } else {
            fout << dist[i] << " ";
        }
    }
    fout << "\n";

    fin.close();
    fout.close();

    return 0;
}