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

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

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

namespace Dijkstra {
    class EdgeEntryComparator {
    public:
        std::vector<int>& cost;
        EdgeEntryComparator(std::vector<int>& _cost) : cost(_cost) {}
        bool operator()(int a,  int b) {
            return this->cost[a] > this->cost[b];
        }
    };
    
    template <typename T = EdgeEntryComparator>
    std::vector<int> dijkstra(const Graph& g, int source) {
        std::vector<int> dist(g.nodes + 1, 1e9);
        T comp = T(dist);
        std::priority_queue<int, std::vector<int>, T> pq(comp);
        std::vector<bool> isinqueue(g.nodes + 1, false);

        dist[source] = 0;
        pq.push(source);
        isinqueue[source] = true;
        while(!pq.empty()) {
            int node = pq.top();
            pq.pop();
            isinqueue[node] = false;
            for (auto& edge : g.graph[node]) {
                int neigh = edge.dest;
                // std:: cout << node << " -> " << neigh << " curent cost: " <<  dist.at(neigh) << "\n";
                if (neigh != node && dist.at(neigh) > dist.at(node) + edge.cost) {
                    // std:: cout << "Adding: " << node << " -> " << neigh << " :: " << edge->cost << "\n";
                    dist.at(neigh) = dist.at(node) + edge.cost;
                    if (isinqueue[neigh] == false) {
                        pq.push(neigh);
                        isinqueue[neigh] = true;
                    }
                }
            }
        }
        for (auto& x : dist) {
            if (x == 1e9)
                x = -1;
        }
        return dist;
    }

    template <typename T = EdgeEntryComparator>
    std::pair< std::vector<int>, std::vector<int> > dijkstra_bef(const Graph& g, int source) {
        std::vector<int> dist(g.nodes + 1, 1e9);
        T comp = T(dist);
        std::priority_queue<int, std::vector<int>, T> pq(comp);
        std::vector<bool> isinqueue(g.nodes + 1, false);
        std::vector<int> bef(g.nodes + 1, -1);
        dist[source] = 0;
        pq.push(source);
        isinqueue[source] = true;
        while(!pq.empty()) {
            int node = pq.top();
            pq.pop();
            isinqueue[node] = false;
            for (auto& edge : g.graph[node]) {
                int neigh = edge.dest;
                // std:: cout << node << " -> " << neigh << " curent cost: " <<  dist.at(neigh) << "\n";
                if (neigh != node && dist.at(neigh) > dist.at(node) + edge.cost) {
                    // std:: cout << "Adding: " << node << " -> " << neigh << " :: " << edge->cost << "\n";
                    dist.at(neigh) = dist.at(node) + edge.cost;
                    if (isinqueue[neigh] == false) {
                        pq.push(neigh);
                        isinqueue[neigh] = true;
                        bef[neigh] = node;
                    }
                }
            }
        }
        for (auto& x : dist) {
            if (x == 1e9)
                x = -1;
        }
        return std::make_pair(dist, bef);
    }
}

template <typename T>
void logvec(std::vector<T> vec, int offset = 0, int n = 2) {
    for (int i = offset; i <= n; ++i) {
        if (vec[i] == -1)
            g <<"0 ";
        else g << vec[i] << " ";
    }
}
template <typename T>
void logvec(T vec[100001], int offset = 0, int n = 2) {
    for (int i = offset; i <= n; ++i) {
        if (vec[i] == -1)
            g <<"0 ";
        else g << vec[i] << " ";
    }
}

int main() {
    int n, m, so = 1;
    f >> n >> m;
    Graph g(n);
    int s, d, c;

    while(f >> s >> d >> c) {
        g.addEdge(s, d, c, 1);
    }

    logvec(Dijkstra::dijkstra(g, so), 2, n);
}