# 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];
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));
    }
}

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;
}

void insertHeap (int nod)
{
    int poz;

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

    while (rez [heap [poz]] > rez [nod])
    {
        change (poz * 2, poz);
        poz /= 2;
    }
}

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

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

    while (! f)
    {
        aux = rez [heap [poz]];
        aux1 = rez [heap [poz * 2]];
        aux2 = rez [heap [poz * 2 + 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;
    }
}

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

    insertHeap (nod);

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

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

            if (muchieC. nod == 5)
                muchieC.nod = 5;

            if (viz [muchieC. nod] == false)
                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] ++;

                    insertHeap (muchieC. nod);
                }
        }

        stergeHeap (1);
    }
}

void afisare ()
{
    int i;

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

void initViz ()
{
    int i;

    for (i = 1; i <= n; i ++)
        viz [i] = false;
}

void bFS (int nod)
{
    int i, aux, poz, pC;

    initViz ();
    q. push (nod);

    while (q. size ())
    {
        pC ++;
        aux = q. front ();
        viz [aux] = true;

        if (aux == 5)
            poz = pC;

        printf ("%d ", aux);

        for (i = 0; i < v [aux]. size (); i ++)
            if (! viz [v [aux] [i]. nod])
                q. push (v [aux] [i]. nod);

        q. pop ();
    }

    printf ("\n%d", poz);
}

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

    return 0;
}