#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

struct weighted_edge {
    int from, dest, weight;
    bool operator<(const weighted_edge& other) const { return weight < other.weight;}
};

std::istream& operator>>(std::istream& inBuff, weighted_edge& edge) { inBuff >> edge.from >> edge.dest >> edge.weight; return inBuff; }

void TopologicalSort() {
    int N, M;
    std::ifstream f("sortaret.in");
    std::ofstream g("sortaret.out");
    f >> N >> M;
    std::list<int> *adj = new std::list<int>[N];
    std::vector<int> grade(N);
    for(int i = 0; i < M; ++i) {
        int X, Y;
        f >> X >> Y;
        adj[X - 1].push_back(Y - 1);
        grade[Y - 1]++;
    }
    std::queue<int> result;
    for(size_t i = 0; i < grade.size(); ++i)
        if(grade[i] == 0)
            result.push(i);
    while(!result.empty()) {
        int st = result.front();
        g << st + 1 << ' ';
        result.pop();
        for(int nod : adj[st]) {
            grade[nod]--;
            if(!grade[nod])
                result.push(nod);
        }
    }
    delete[] adj;
    f.close();
    g.close();
}

void BellmanFord() {
    int N, M, S = 1;
    std::ifstream f("bellmanford.in");
    std::ofstream g("bellmanford.out");
    f >> N >> M;
    std::list<std::pair<int, int>> *adj = new std::list<std::pair<int, int>>[N];
    for(int i = 0; i < M; ++i) {
        int X, Y, C;
        f >> X >> Y >> C;
        adj[X - 1].push_back({Y - 1, C});
    }
    std::vector<int> result(N, INT_MAX);
    std::vector<int> relax(N, 0);
    std::queue<int> Q;
    result[S - 1] = 0;
    Q.push(S - 1);
    while(!Q.empty()) {
        int s = Q.front();
        relax[s]++;
        if(relax[s] == N) {
            g << "Ciclu negativ!";
            return;
        }
        Q.pop();
        for(auto nod : adj[s])
            if(result[s] + nod.second < result[nod.first]) {
                result[nod.first] = result[s] + nod.second;
                Q.push(nod.first);
            }
    }
    for(int i = 1; i < N; ++i)
        g << result[i] << ' ';
    f.close();
    g.close();
}

int root(int x, std::vector<int>& father) {
    if(x == father[x])
        return x;
    else
        return father[x] = root(father[x], father);
}

void Kruskal() {
    int N, M, TW = 0;
    std::ifstream f("kruskal.in");
    std::ofstream g("kruskal.out");
    f >> N >> M;
    std::vector<weighted_edge> edges;
    for(int i = 0; i < M; ++i) {
        weighted_edge edge;
        f >> edge;
        edges.push_back(edge);
    }
    std::sort(edges.begin(), edges.end());
    std::vector<int> father(N);
    for(int i = 0; i < N; ++i)
        father[i] = i;
    std::vector<weighted_edge> result;
    for(weighted_edge edge : edges) {
        if(result.size() == N - 1)
            break;
        int rootf = root(edge.from, father);
        int rootd = root(edge.dest, father);
        if(rootf != rootd) {
            result.push_back(edge);
            father[rootd] = rootf;
            TW += edge.weight;
        }
    }
    g << TW << '\n';
    g << result.size() << '\n';
    for(weighted_edge edge : result)
        g << edge.from + 1 << ' ' << edge.dest + 1 << '\n';
    f.close();
    g.close();
}

void Prim() {
    int V, E, S = 0;
    std::ifstream f("prim.in");
    std::ofstream g("prim.out");
    f >> V >> E;
    std::list<std::pair<int, int>> *adj = new std::list<std::pair<int, int>>[V];
    for(int i = 0; i < E; ++i) {
        weighted_edge edge;
        f >> edge;
        adj[edge.from].push_back({edge.weight, edge.dest});
        adj[edge.dest].push_back({edge.from, edge.dest});
    }
    std::vector<bool> inMST(V, false);
    std::vector<int> dist(V, INT_MAX);
    std::vector<std::pair<int, int>> result;
    std::priority_queue<std::pair<int, int>> Q;
    Q.push({0, S});
    dist[S] = 0;
    while(!Q.empty()) {
        int s = Q.top().second;
        Q.pop();
        inMST[s] = true;
        for(auto node : adj[s])
            if(!inMST[node.second] && dist[node.second] > node.first) {
                dist[node.second] = node.first;
                Q.push({dist[node.second], node.second});
                result.push_back({s, node.second});
            }
    }
    for(auto edge : result)
        g << edge.first << ' ' << edge.second << '\n';
    delete[] adj;
    f.close();
    g.close();
}

void Dijkstra() {
    int V, E, S = 0;
    std::ifstream f("dijkstra.in");
    std::ofstream g("dijkstra.out");
    f >> V >> E;
    std::list<std::pair<int, int>> *adj = new std::list<std::pair<int, int>>[V];
    for(int i = 0; i < E; ++i) {
        weighted_edge edge;
        f >> edge;
        adj[edge.from - 1].push_back({edge.weight, edge.dest - 1});
    }
    std::vector<int> dist(V, INT_MAX);
    std::priority_queue<std::pair<int, int>> Q;
    Q.push({0, S});
    dist[S] = 0;
    while(!Q.empty()) {
        int s = Q.top().second;
        Q.pop();
        for(auto node : adj[s])
            if(dist[node.second] > node.first + dist[s]) {
                dist[node.second] = node.first + dist[s];
                Q.push({dist[node.second], node.second});
            }
    }
    for(int d  = 1; d < V; ++d)
        g << dist[d] << ' ';
    delete[] adj;
}

int main() {
    //TopologicalSort();
    //BellmanFord();
    //Kruskal();
    //Prim();
    Dijkstra();
    return 0;
}