#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50000, oo = 1000000000;

int D[NMAX + 5], N, M;

bool Use[NMAX + 5];

vector <pair<int, int> > G[NMAX + 5];

void Read()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i++) {
        int x, y, c;

        fin >> x >> y >> c;

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

void Dijkstra()
{
    for(int i = 2; i <= N; i++)
        D[i] = oo;

    for(int k = 1; k <= N; k++) {
        int Min = oo,  Nod;

        //Alegere
        for(int i = 1; i <= N; i++)
            if(D[i] < Min && !Use[i]) {
                Min = D[i];
                Nod = i;
            }
        Use[Nod] = true;

        //Relaxare
        for(int i = 0; i < G[Nod].size(); i++) {
            int Vecin = G[Nod][i].first, Cost = G[Nod][i].second;

            D[Vecin] = min(D[Vecin], D[Nod] + Cost);
        }
    }
}

void Print()
{
    for(int i = 2; i <= N; i++)
        fout << D[i] << " ";

    fout << '\n';
}

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

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

    return 0;
}