#include <fstream>
#include <climits>
#include <vector>

#define MAXN 50012

using namespace std;

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

struct two{
    int nod, c;
};

vector <two> G[MAXN];

int heap[MAXN], d[MAXN], viz[MAXN], n, nn, left_son, right_son, poz, fr[MAXN], father;
int varf;

inline void Read()
{
    int m, x, y, z;

    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;

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

inline void Initializer()
{
    for (int i = 2; i <= n; i++)
        d[i] = heap[i] = INT_MAX;

    heap[1] = 1;
    fr[1] = 1; nn = 1;
}

inline void up(int son)
{
    while (son > 1)
    {
        father = son / 2;

        if (d[heap[father]] > d[heap[son]])
        {
            swap(fr[heap[father]], fr[heap[son]]);

            swap(heap[father], heap[son]);
        }

        son = father;
    }
}

inline void down(int father)
{
    while (father <= nn)
    {
        left_son = father * 2;
        right_son = father * 2 + 1;
        poz = 0;

        if (left_son <= nn)
            poz = left_son;
        if (right_son <= nn)
        {
            if (d[heap[left_son]] > d[heap[right_son]])
                poz = right_son;
        }

        if (poz)
        {
            if (d[heap[father]] > d[heap[poz]])
            {
                swap(fr[heap[father]], fr[heap[poz]]);

                swap(heap[father], heap[poz]);

                father = poz;
            }
            else
                return;
        }
        else
            return;
    }
}

inline void Dijkstra()
{
    while (nn)
    {
        varf = heap[1];

        for (vector <two> :: iterator i = G[varf].begin(); i != G[varf].end(); i++)
        {
            if (d[varf] + (*i).c < d[(*i).nod] && viz[(*i).nod] == 0)
            {
                d[(*i).nod] = d[varf] + (*i).c;

                if (fr[(*i).nod])
                {
                    up(fr[(*i).nod]);
                }
                else
                {
                    fr[(*i).nod] = ++nn;

                    heap[nn] = (*i).nod;

                    up(nn);
                }
            }
        }

        viz[varf] = 1;

        heap[1] = heap[nn];

        nn--;

        down(1);
    }
}

inline void Write()
{
    for (int i = 2; i <= n; i++)
    {
        if (d[i] == INT_MAX)
            d[i] = 0;

        fout << d[i] << " ";
    }
}

int main ()
{
    Read();
    Initializer();
    Dijkstra();
    Write();

    fin.close(); fout.close(); return 0;
}