#include <cstdio>
#define DIM 50005
const int INF = (1<<30);
struct nod
{
    int x, cost;
    nod *next;
};

nod *G[DIM];
int v[DIM], vpoz[DIM], h[DIM], lh, n, m, d[DIM];


void add(int i, int j, int c)
{
    nod *p = new nod;
    p->x = j;
    p->cost = c;
    p->next = G[i];
    G[i] = p;

}

void afis_heap()
{
    for (int i = 1; i <= lh; ++i)
        printf ("%d ", i);
    printf ("\n");

    for (int i = 1; i <= lh; ++i)
        printf ("%d ", h[i]);

    printf ("\n||--------||\n");

}

void afis()
{
    for (int i = 1; i <= n; ++i)
    {
        printf ("%d: ", i);
        for (nod *p = G[i]; p; p = p -> next)
            printf ("%d ", p->x);
        printf ("\n");
    }
}

void swap(int &a, int &b)
{
    int aux = a;
    a = b;
    b = aux;
}

void insus(int i)
{
    while (i > 1 && d[h[i]] < d[h[i/2]])
    {
        swap(h[i], h[i/2]);
        vpoz[h[i]] = i;
        vpoz[h[i/2]] = i/2;
        i /= 2;
    }

}

void injos(int i)
{
    int j;
    while (2*i <= lh && ((d[h[i]] > d[h[2*i]]) || (d[h[i]] > d[h[2*i+1]])))
    {
        j = 2 * i;
        if (d[h[j]] > d[h[j+1]] && j+1<=lh)
            ++j;

        swap(h[i], h[j]);
        vpoz[h[i]] = i;
        vpoz[h[j]] = j;
        i = j;
    }
}

void sterge(int i)
{
    h[i] = h[lh--];
    injos(i);
}

void dijkstra()
{
    lh = n;
    for (int i = 1; i <= n; ++i)
    {
        h[i] = i;
        vpoz[i] = i;
        d[i] = INF;
        v[i] = 0;
    }

    //nod start = 1 initializare
    v[1] = 1;
    d[1] = 0;
    sterge(1);
    for (nod *p = G[1]; p; p = p -> next )
        d[p->x] = p->cost, insus(vpoz[p->x]);

 //   afis_heap();
    for (int q = 1, min; q < n; ++q)
    {
        min = h[1];
        sterge(1);
        if (d[min] == INF)
            break;
        v[min] = 1;
        for (nod *p = G[min]; p; p = p -> next)
            if (!v[p->x] && d[p->x] > d[min] + p->cost)
                d[p->x] = d[min] + p->cost, insus(p->x);


    }

}

int main()
{
    FILE *f = fopen("dijkstra.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int i = 1, x, y, c; i <= m; ++i)
    {
        fscanf(f, "%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    afis();
    dijkstra();
    fclose(f);
    f = fopen("dijkstra.out", "w");
    for (int i = 2; i <= n; ++i)
        fprintf (f, "%d ", d[i]==INF?0:d[i]);

    return 0;
}