#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");
class Edge {
    public:
        long long source;
        long long dest;
        long long cost;
    Edge() : source(0), dest(0) {}
    Edge(long long _s) : source(-1), dest(_s), cost(0) {}
    Edge(long long _source, long long _dest, long long _cost) : source(_source), dest(_dest), cost(_cost) {}
};

class EdgeComparator {
public:
    bool operator()(Edge a,  Edge b) {
        return a.cost > b.cost;
    }
};

class Graph {
public:
    long long nodes;
    std::vector < std::vector<Edge *> > graph;
    Graph(long long n) {
        for (int i = 0 ; i < 1 + n ; ++i) 
            graph.push_back(std::vector<Edge *>());
        nodes = n;
    }
    void addEdge(long long s, long long d, long long c, int directed=1) {
        Edge *e1 = new Edge(s, d, c);
        graph[s].push_back(e1);
        if (directed == 0) {
            Edge *e2 = new Edge(d, s, c);
            graph[d].push_back(e2);
        }
    }
};

class EdgeEntry {
    public:
        long long source;
        long long dest;
        long long cost;
    EdgeEntry() : source(0), dest(0) {}
    EdgeEntry(long long _s) : source(-1), dest(_s), cost(0) {}
    EdgeEntry(long long _source, long long _dest, long long _cost) : source(_source), dest(_dest), cost(_cost) {}
};

class EdgeEntryComparator {
public:
    bool operator()(EdgeEntry a,  EdgeEntry b) {
        return a.cost > b.cost;
    }
};

std::vector<int> dijkstra(Graph g, long long source) {
    std::priority_queue<EdgeEntry, std::vector<EdgeEntry>, EdgeEntryComparator> pq;
    std::vector<int> viz(g.nodes + 1, 0);
    std::vector<int> dist(g.nodes + 1, 1e9);
    std::vector<int> bef(g.nodes + 1, 0);
    pq.push(EdgeEntry(source));
    dist.at(source) = 0;
    while(!pq.empty()) {
        EdgeEntry curr = pq.top();
        pq.pop();
        long long node = curr.dest;
        viz.at(node) = 2;

        int min_neigh = -1, min_dist = 1e9;
        for (auto& edge : g.graph[node]) {
            long long neigh = edge->dest;
            // std:: cout << node << " -> " << neigh << " curent cost: " <<  dist.at(neigh) << "\n";
            if (neigh != node && viz[neigh] == 0 && dist.at(neigh) > dist.at(node) + edge->cost) {
                dist.at(neigh) = dist.at(node) + edge->cost;
                bef.at(neigh) = node;
            }
            if (viz[neigh] == 0 && dist[neigh] < min_dist && neigh != node) {
                min_dist = dist[neigh];
                min_neigh = neigh;
            }
        }

        if (min_neigh != -1) {
            // std:: cout << "- Queued: " << node << " -> " << min_neigh << " :: " << dist[min_neigh] << "\n";
            pq.push(EdgeEntry(node, min_neigh, dist[min_neigh]));
        }


    }
    for (auto& x : dist) {
        if (x == 1e9)
            x = -1;
    }
    return dist;
}

template <typename T>
void logvec(std::vector<T> vec, int offset = 0) {
    for (int i = offset; i < vec.size(); ++i) {
        g << vec[i] << " ";
    }
}

int main() {
    int n, m, so = 1;
    f >> n >> m;
    Graph g(n);
    for (int i = 0; i < m ; ++i) {
        int s, d, c;
        f >> s >> d >> c;
        g.addEdge(s, d, c, 0);
    }
    logvec(dijkstra(g, so), 2);
}