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

#define MAXN 50004

using namespace std;

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

struct punct{
    int graf, c;
};

vector <punct> G[MAXN];

int n, m, x, y, z;
punct heap[MAXN * 3];
int fr[MAXN], cost[MAXN], nn, viz[MAXN];

inline void Read()
{
    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 constr_heap()
{
    for (int i = 1; i <= n; i++)
    {
        heap[i].c = INT_MAX;
        heap[i].graf = i;
        fr[i] = i;
        cost[i] = INT_MAX;
    }
    heap[1].c = 0;
}

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;

    while (father <= nn)
    {
        left_son = father * 2;
        right_son = father * 2 + 1;

        if (right_son <= nn)
        {
            if (heap[left_son].c < heap[right_son].c && heap[father].c > heap[left_son].c)
            {
                fr[heap[father].graf] = left_son;
                fr[heap[left_son].graf] = father;

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

                father = left_son;
            }
            else if (heap[right_son].c < heap[father].c && heap[left_son].c > heap[right_son].c)
            {
                fr[heap[father].graf] = right_son;
                fr[heap[right_son].graf] = father;

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

                father = right_son;
            }
            else
                return;
        }
        else if (left_son <= nn)
        {
            if (heap[father].c > heap[left_son].c)
            {
                fr[heap[father].graf] = left_son;
                fr[heap[left_son].graf] = father;

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

                father = left_son;
            }
            else
                return;
        }
        else
            return;
    }
}

inline void Solve()
{
    int cmin, gr;
    nn = n;
    for (int i = 1; i <= n; i++)
    {
        cmin = heap[1].c;
        gr = heap[1].graf;

        viz[gr] = 1;
        fr[gr] = 0;

        heap[1] = heap[nn];
        nn--;

        down(1);

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

                    heap[fr[(*j).graf]].c = cost[(*j).graf];

                    up(fr[(*j).graf]);
                }
            }
        }
    }
}

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

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

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

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