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

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <int> vector_vecini[50001];
vector <int> vecin_cost[50001];
priority_queue<pair<int, int> > myheap;
int distanta[50001];
int vizitat[50001];

void afisare_coada(priority_queue <pair<int, int> >queue) {
    while (!queue.empty()) {
        if (queue.top().first< -1000)
            cout << "-INF" << " " << queue.top().second << "  ";
        else
            cout << queue.top().first << " " << queue.top().second << " ";
        queue.pop();
    }
    cout << '\n';
}

int main() {
    int N, M, x, y, c, i, k, index;
    fin >> N >> M;
    for (i = 1; i <= M; i++) {
        fin >> x >> y >> c;
        vector_vecini[x].push_back(y);
        vecin_cost[x].push_back(c);
    }

    for (i = 1; i <= N; i++) {
        if (i == 1)
            distanta[i] = 0;
        else
            distanta[i] = INT_MAX;
        myheap.push(make_pair(-distanta[i], i));
        afisare_coada(myheap);

    }
    while (!myheap.empty()) {
        pair<int, int>p = myheap.top();
        index = p.second;
        myheap.pop();
        if (vizitat[index] == 1);
        else {
            vizitat[index] = 1;

            int lim = vector_vecini[index].size();
            for (k = 0; k < lim; k++) {

                int nod_vecin = vector_vecini[index][k];
                if (distanta[nod_vecin] > (distanta[index] + vecin_cost[index][k])) {
                    distanta[nod_vecin] = distanta[index] + vecin_cost[index][k];
                    myheap.push(make_pair(-distanta[nod_vecin], nod_vecin));
                    cout << "\nheap: ";
                    afisare_coada(myheap);
                    cout << endl;
                }
            }

        }

    }
    for (i = 2; i <= N; i++) {
        if (distanta[i] == INT_MAX)
            distanta[i] = -1;
        fout << distanta[i] << " ";
    }
    return 0;
}