#include <bits/stdc++.h>
#define infinit (1 << 30)
using namespace std;

const int kNmax = 50005;
const int kInf = 0x3f3f3f3f;


class Task {
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    int n;
    int m;
    int source;
    vector<pair<int, int> > adj[kNmax];
    vector<int> parent;

    void read_input() {
        source = 1;
        ifstream fin("dijkstra.in");
        fin >> n >> m;
        parent.resize(n + 1);
        for (int i = 1, x, y, w; i <= m; i++) {
            fin >> x >> y >> w;
            adj[x].push_back(make_pair(y, w));
        }
        fin.close();
    }

    vector<int> get_result() {
        /*
        TODO: Gasiti distantele minime de la nodul source la celelalte noduri
        folosind Dijkstra pe graful orientat cu n noduri, m arce stocat in adj.
            d[node] = costul minim / lungimea minima a unui drum de la source la nodul
        node;
            d[source] = 0;
            d[node] = -1, daca nu se poate ajunge de la source la node.

        Atentie:
        O muchie este tinuta ca o pereche (nod adiacent, cost muchie):
            adj[x][i].first = nodul adiacent lui x,
            adj[x][i].second = costul.
        */
        vector<int> d(n + 1, infinit); // distanta e infinit
        priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> pq;
        d[source] = 0;
        pq.push({d[source], source});
        while (!pq.empty()) {
            auto it = pq.top();
            pq.pop();
            int cost = it.first; // costu din heap
            int currentNode = it.second; // nodul efectiv din heap
            for (uint i = 0; i < adj[currentNode].size(); ++i) {
                int nextNode = adj[currentNode][i].first; // urmatorul nod
                int cost_edge = adj[currentNode][i].second; // costu pana la urmatorul nod
                if (d[nextNode] > d[currentNode] + cost_edge) {
                    d[nextNode] = d[currentNode] + cost_edge;
                    parent[nextNode] = currentNode;
                    pq.push({d[nextNode], nextNode});
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (d[i] == infinit) {
                d[i] = -1;
            }
        }
        return d;
    }

    std::vector<int> getRoad(int node) {
        std::vector<int> path;
        while (node != 0) {
            path.push_back(node);
            node = parent[node];
        }
        return path;
    }

    void print_output(vector<int> result) {
        ofstream fout("dijkstra.out");
        for (int i = 1; i <= n; i++) {
            fout << result[i] << " ";
        }
        fout << "\n";
        fout.close();
    }
};

// Please always keep this simple main function!
int main() {
    // Allocate a Task object on heap in order to be able to 
    // declare huge static-allocated data structures inside the class.
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}