#include <cassert>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <set>

#define INF INT_MAX

using namespace std;

class Graph{
    private:
        int n, m;
        vector< vector< pair< int, int > > > G;
    public:
        int getN();
        int getM();
        vector< pair< int, int > >& operator[](int);

        friend istream& operator>>(istream& , Graph&);
};

int Graph::getN() {
    return n;
}

int Graph::getM() {
    return m;
}

vector< pair< int, int > >& Graph::operator[](const int i) {
    assert(i >= 1 && i <= n);

    return G[i];
}

istream& operator>>(istream& in, Graph& obj) {
    in >> obj.n >> obj.m;
    obj.G.reserve(obj.n + 1);
    obj.G.resize(obj.n + 1);
    int x, y, z;
    for (int i = 0; i < obj.m; ++i) {
        in >> x >> y >> z;
        obj.G[x].push_back(make_pair(y, z));
    }
    return in;
}

class Dijkstra{
    private:
        int n, m;
        int *tata, *d;
    public:
        explicit Dijkstra(Graph& G);
        ~Dijkstra();

        friend ostream& operator<<(ostream& , const Dijkstra&);
};

Dijkstra::Dijkstra(Graph& A) {
    n = A.getN();
    m = n - 1;
    d = new int[n + 1];
    tata = new int[n + 1];
    int* viz = new int[n + 1];
    fill(viz, viz + n + 1, 0);
    int start = 1;
    for (int i = 1; i <= n ; ++i) {
        d[i] = INF;
    }
    d[start] = 0;
    vector<int> S;
    //priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > Q;
    set<pair<int,int>> Q;
    Q.insert(make_pair(d[start], start));
    while (!Q.empty()) {
        int u = Q.begin()->second;
        Q.erase(Q.begin());
        if(viz[u] == 0) {
            for (int i = 0; i < A[u].size(); i++) {
                int v = A[u][i].first;
                int Wuv = A[u][i].second;
                if (viz[v] == 0 && d[v] > d[u] + Wuv) {
                    d[v] = d[u] + Wuv;
                    Q.insert(make_pair(d[v], v));
                }
            }
        }
        viz[u] = 1;
    }
    delete[] viz;
}

Dijkstra::~Dijkstra() {
    delete[] d;
    delete[] tata;
}

ostream& operator<<(ostream& out, const Dijkstra& obj) {
    for(int i = 2; i <= obj.n; ++i)
        (obj.d[i] != INF) ? out << obj.d[i] << ' ' : out << 0 << ' ';
    return out;
}

int main() {
    ifstream fin("dijkstra.in");
    if(!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    Graph *G = new Graph();
    fin >> *G;
    //cout << G.G[1][0].first;
    Dijkstra *D = new Dijkstra(*G);

    ofstream fout("dijkstra.out");
    if(!fout.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    fout << *D << '\n';

    fin.close();
    fout.close();
    return 0;
}