#include <iostream>
#include <fstream>

#define MAXN 50005
#define INF 1 << 30

using namespace std;

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

int n, m;
int d[MAXN], h[MAXN], poz[MAXN], k;

struct NOD
{
    int info;
    int cost;
    NOD *next;
} *gr[MAXN];

void add(int a, int b, int c)
{
    NOD *q = new NOD;
    q->info = b;
    q->cost = c;
    q->next = gr[a];
    gr[a] = q;
}

void swaph(int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void percolate(int x)
{
    int father;
    while (x > 1)
    {
        father = x >> 1;

        if (d[h[father]] > d[h[x]])
        {
            poz[h[x]] = father;
            poz[h[father]] = x;

            swaph(father, x);

            x = father;
        }
        else
            x = 1;
    }
}

void sift(int x)
{
    int son;
    while (son <= k)
    {
        son = x;
        if ((x << 1) <= k)
        {
            son = x << 1;
            if (son + 1 <= k)
                if (d[h[son + 1]] < d[h[son]])
                    son++;
        }
        else return;

        if (d[h[x]] > d[h[son]])
        {
            poz[h[x]] = son;
            poz[h[son]] = x;

            swaph(x, son);

            x = son;
        }
        else return;
    }
}

void dijkstra()
{
    for (int i = 2; i <= n; ++i)
    {
        d[i] = INF;
        poz[i] = -1;
    }

    poz[1] = 1;
    h[++k] = 1; // il adaug pe 1 in heap

    while (k) // am noduri in heap
    {
        int minim = h[1];
        swaph(1, k);
        poz[h[1]] = 1;
        --k;

        sift(1);

        NOD *q = gr[minim];

        while (q)
        {
            if (d[q->info] > d[minim] + q->cost)
            {
                d[q->info] = d[minim] + q->cost;

                if (poz[q->info] != -1)
                    percolate(poz[q->info]);
                else
                {
                    h[++k] = q->info;
                    poz[h[k]] = k;
                    percolate(k);
                }
            }
            q = q->next;
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        fin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    for (int i = 2; i <= n; ++i)
        fout << (d[i] == INF ? 0 : d[i]) << ' ';

    return 0;
}