#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];

int main() {
    int N, M, A, B, C, i, k, index;
    fin >> N >> M;
    for (i = 1; i <= M; i++) {
        fin >> A >> B >> C;
        vector_vecini[A].push_back(B);
        vecin_cost[A].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));

    }
    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));
                }
            }

        }

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