# include <cstdio>
# include <vector>
# include <queue>

using namespace std;

const int N = 50000;

struct Muchie
{
    int nod, cost;
};

Muchie getMuchie (int nod, int cost)
{
    Muchie m;

    m. nod = nod;
    m. cost = cost;

    return m;
}

vector <Muchie> v [N + 1];
queue <int> q;
int rez [N + 1], heap [N + 1], pHeap [N + 1];
bool viz [N + 1];
int n, m, lHeap;

void citeste ()
{
    int i, n1, n2, c;

    scanf ("%d %d", & n, & m);

    for (i = 1; i <= m; i ++)
    {
        scanf ("%d %d %d", & n1, & n2, & c);
        v [n1]. push_back (getMuchie (n2, c));
        if (n2 == 698)
            n2 = 698;
    }
}

void initRez ()
{
    int i;

    for (i = 0; i <= n; i ++)
        rez [i] = - 1;
}

void init ()
{
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);
    citeste ();
    initRez ();
}

void change (int poz1, int poz2)
{
    int aux = heap [poz1];

    heap [poz1] = heap [poz2];
    heap [poz2] = aux;
    pHeap [heap [poz1]] = poz1;
    pHeap [heap [poz2]] = poz2;
}

void insertHeap (int nod)
{
    int poz;
    bool f;

    heap [++ lHeap] = nod;
    pHeap [nod] = lHeap;
    poz = lHeap / 2;

    if (lHeap % 2 == 1)
        f = true;
    else
        f = false;

    while (rez [heap [poz]] > rez [nod])
    {
        if (f == false)
            change (poz * 2, poz);
        else
            change (poz * 2 + 1, poz);

        if (poz % 2 == 1)
            f = true;
        else
            f = false;

        poz /= 2;
    }
}

void stergeHeap (int p)
{
    int poz = p, aux, aux1, aux2;
    bool f = false;

    if (p == 0)
        return;

    pHeap [heap [p]] = 0;
    heap [p] = heap [lHeap --];
    pHeap [heap [p]] = p;

    while (! f)
    {
        aux = rez [heap [poz]];
        aux1 = rez [heap [poz * 2]];
        aux2 = rez [heap [poz * 2 + 1]];

        if (poz * 2 > lHeap)
            aux1 = aux2 = - 1;
        else
            if (poz * 2 + 1 > lHeap)
                aux2 = - 1;

        if (aux1 < aux2 && aux1 != - 1)
            if (aux1 < aux)
            {
                change (poz, poz * 2);
                poz *= 2;
            }
            else
                f = true;
        else
            if (aux2 < aux && aux2 != - 1)
            {
                change (poz, poz * 2 + 1);
                poz = poz * 2 + 1;
            }
            else
                f = true;
    }
}

bool apartineHeap (int x)
{
    int i;

    for (i = 1; i <= lHeap; i ++)
        if (heap [i] == x)
            return true;

    return false;
}

void dijkstra (int nod)
{
    int i, nodC;
    Muchie muchieC;

    insertHeap (nod);

    while (lHeap)
    {
        nodC = heap [1];
        viz [nodC] = true;

        if (nodC == 921)
            i ++;

        for (i = 0; i < v [nodC]. size (); i ++)
        {
            muchieC = v [nodC] [i];

            if (muchieC. nod == 698)
                i ++, i --;

            if (rez [muchieC. nod] == - 1 || rez [nodC] + muchieC. cost < rez [muchieC. nod])
            {
                rez [muchieC. nod] = rez [nodC] + muchieC. cost;

                if (nodC == 1)
                    rez [muchieC. nod] ++;

                stergeHeap (pHeap [muchieC. nod]);
                insertHeap (muchieC. nod);
            }
        }

        if (heap [1] != nodC)
            i = 0;

        stergeHeap (1);
    }
}

void afisare ()
{
    int i;

    for (i = 2; i <= n; i ++)
        if (rez [i] < 0)
            printf ("0 ");
        else
            printf ("%d ", rez [i]);
}

int main ()
{
    init ();
    dijkstra (1);
    afisare ();

    return 0;
}