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

#define MAXN 50004

using namespace std;

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

struct punct{
    int c, graf;
};

vector <punct> G[MAXN];

punct heap[MAXN];

int n, m, cost[MAXN], fr[MAXN], nn, viz[MAXN];

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

    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        G[x].push_back({z, y});
    }
}

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

        if (heap[father].c > heap[son].c)
        {
            fr[heap[father].graf] = son;
            fr[heap[son].graf] = father;
            swap(heap[father], heap[son]);

            son = father;
        }
        else
            return;
    }
}

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

    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 (heap[right_son].c < heap[left_son].c)
                poz++;
        }

        if (heap[poz].c < heap[father].c && poz)
        {
            fr[heap[poz].graf] = father;
            fr[heap[father].graf] = poz;

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

            father = poz;
        }
        else
            return;
    }
}

inline void Solve()
{
    for (int i = 1; i <= n; i++)
    {
        cost[i] = INT_MAX;
    }

    heap[1] = {0, 1};
    cost[1] = 0;
    nn = 1;

    int gr;

    while (nn > 0)
    {
        gr = heap[1].graf;

        for (vector <punct> :: iterator i = G[gr].begin(); i != G[gr].end(); i++)
        {
            if (viz[(*i).graf] == 0)
            {
                if (cost[gr] + (*i).c < cost[(*i).graf])
                {
                    cost[(*i).graf] = cost[gr] + (*i).c;

                    if (fr[(*i).graf] != 0)
                    {
                        heap[fr[(*i).graf]].c = cost[(*i).graf];

                        up(fr[(*i).graf]);
                    }
                    else
                    {
                        heap[++nn].c = cost[(*i).graf];
                        heap[nn].graf = (*i).graf;
                        fr[heap[nn].graf]  = nn;

                        up(nn);
                    }
                }
            }
        }

        viz[gr] = 1;

        heap[1] = heap[nn];
        fr[heap[1].graf] = 1;
        nn--;

        down(1);
    }
}

inline void Afisare()
{
    for (int i = 2; i <= n; i++)
    {
        if (cost[i] == INT_MAX)
        {
            cost[i] = 0;
        }

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

int main ()
{
    Read();
    Solve();
    Afisare();

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