#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000, oo = 1e9;

struct st{int vc; int c;};

struct {int val; int nume;} Heap[NMAX + 5];
///nodul nume este la dist val de radacina

vector <st> G[NMAX + 5];

int Poz[NMAX + 5], D[NMAX + 5], N, M, K; ///Poz[i] = pozitia in Heap a nodului i

bool Use[NMAX + 5];

void Up(int i)
{
    while(i > 1 && Heap[i].val < Heap[i / 2].val) {
        swap(Poz[Heap[i].nume], Poz[Heap[i / 2].nume]);
        swap(Heap[i], Heap[i / 2]);

        i /= 2;
    }
}

void Down(int i)
{
    int son = 1;

    while(son) {
        son = 0;

        if(2 * i <= K && Heap[2 * i].val < Heap[i].val)
            son = 2 * i;

        if(2 * i + 1 <= K && Heap[2 * i + 1].val < Heap[i].val && Heap[2 * i + 1].val< Heap[2 * i].val)
            son = 2 * i + 1;

        if(son) {
            swap(Poz[Heap[i].nume], Poz[Heap[son].nume]);
            swap(Heap[i], Heap[son]);
            i = son;
        }
    }
}

void Delete(int i)
{
    Heap[i] = Heap[K], Poz[Heap[K].nume] = Poz[Heap[i].nume], K--;

    Up(i);
    Down(i);
}

void Read()
{
    int ct, x, y;

    fin >> N >> M;

    K = N;

    for(int i = 0; i < M; i++) {
        fin >> x >> y >> ct;

        G[x].push_back({y, ct});
    }
}

void Dijkstra()
{
    ///initializare
    for(int i = 2; i <= N; i++)
        Heap[i] = {oo, i}, D[i] = oo, Poz[i] = i;

    Heap[1] = {0, 1}, Poz[1] = 1;

    for(int i = 1; i < N; i++) {
        ///alegere
        int Nod = Heap[1].nume, distnod = Heap[1].val;

        Delete(1);

        ///relaxare
        for(int j = 0; j < (int)G[Nod].size(); j++) {
            int cost = G[Nod][j].c, Vecin = G[Nod][j].vc;

            int distvc = D[Vecin];

            if(distnod + cost < distvc) {
                D[Vecin] = distnod + cost;
                Heap[Poz[Vecin]].val = D[Vecin];

                Up(Poz[Vecin]);
            }
        }
    }
}

void Print()
{
    for(int i = 2; i <= N; i++) {
        if(D[i] == oo)
            fout << "0 ";
        else
            fout << D[i] << " ";
    }

    fout << '\n';
}

int main()
{
    Read();
    Dijkstra();
    Print();

    fin.close();
    fout.close();

    return 0;
}