#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct heap
{
    int val, nod;
};
heap *H;

struct muchie
{
    int nod, cost;
};

int N, M, muchii;
int *posH, *T, *D;
vector<vector<muchie> > V;
bool *inH;

int tata(int nod)
{
    return nod / 2;
}

int fiu_stang(int nod)
{
    return 2 * nod;
}

int fiu_drept(int nod)
{
    return 2 * nod + 1;
}

void urca(int nod)
{
    while ((nod > 1) && H[nod].val < H[tata(nod)].val)
    {
        swap(H[nod], H[tata(nod)]);
        swap(posH[H[nod].nod], posH[H[tata(nod)].nod]);
        nod = tata(nod);
    }
}

void coboara(int nod)
{
    int fiu = 1;
    while (fiu)
    {
        fiu = 0;
        if (fiu_stang(nod) <= M)
        {
            fiu = fiu_stang(nod);
            if (fiu_drept(nod) <= M && H[fiu_drept(nod)].val < H[fiu_stang(nod)].val)
                fiu = fiu_drept(nod);
            if (H[fiu].val >= H[nod].val)
                fiu = 0;
        }

        if (fiu)
        {
            swap(H[nod], H[fiu]);
            swap(posH[H[nod].nod], posH[H[fiu].nod]);

            nod = fiu;
        }
    }
}

void rezolvare(int s)
{
    for (int i = 1; i <= N; ++i)
        D[i] = 2000000000;
    D[s] = 0;

    inH[s] = true;
    ++M;
    H[M].val = 0;
    H[M].nod = s;
    posH[s] = M;

    while (M != 0)
    {
        int nod = H[1].nod;
        swap(H[1], H[M]);
        swap(posH[H[1].nod], posH[H[M].nod]);
        --M;
        coboara(1);

        int lg = V[nod].size();
        for (int i = 0; i <= lg - 1; ++i)
        {
            if (D[nod] + V[nod][i].cost < D[V[nod][i].nod])
            {
                D[V[nod][i].nod] = D[nod] + V[nod][i].cost;
                T[V[nod][i].nod] = nod;

                if (inH[V[nod][i].nod])
                {
                    H[posH[V[nod][i].nod]].val = D[V[nod][i].nod];
                    urca(posH[V[nod][i].nod]);
                }
                else
                {
                    inH[V[nod][i].nod] = true;
                    ++M;
                    H[M].val = D[V[nod][i].nod];
                    H[M].nod = V[nod][i].nod;
                    posH[V[nod][i].nod] = M;
                }
            }
        }
    }
}

int main()
{
    fin >> N >> muchii;
    V.resize(N + 1);
    D = new int[N + 1];
    posH = new int[N + 1];
    H = new heap[2 * N + 2];
    T = new int[N + 1];
    inH = new bool[N + 1];

    for (int i = 1; i <= N; ++i)
    {
        posH[i] = 0;
        T[i] = 0;
        inH[i] = false;
    }

    for (int i = 1; i <= 2 * N + 1; ++i)
    {
        H[i].nod = 0;
        H[i].val = 2000000000;
    }

    for (int i = 1, nod1, nod2, cost; i <= muchii; ++i)
    {
        fin >> nod1 >> nod2 >> cost;
        muchie m;
        m.nod = nod2;
        m.cost = cost;
        V[nod1].push_back(m);
    }

    rezolvare(1);

    for (int i = 2; i <= N; ++i)
    {
        if (D[i] != 2000000000)
            fout << D[i] << ' ';
        else
            fout << 0 << ' ';
    }

    return 0;
}