#include <cstdio>
#define DIM 50005

const int INF = 1<<30;

struct nod
{
    int capat, cost;
    nod *next;
} *v[DIM];

int n, m, dist[DIM], viz[DIM], s;

int smallest()
{
    int min = INF, ibun;
    for (int i = 1; i <= n; ++i)
        if (!viz[i])
            if (dist[i] < min)
                min = dist[i], ibun = i;

    return ibun;
}

bool gata()
{
    for (int i = 1; i <= n; ++i)
        if (!viz[i])
            return false;
    return true;
}


void dijkstra()
{
    dist[1] = 0;
    nod *t;
    int i;
    while (!gata()) //cat timp nu is vizitate toate nodurile
    {
        i = smallest();

        t = v[i];
        viz[i] = 1;

        while (t != NULL)
        {
            if (!viz[t->capat])
                if (dist[i] + t->cost < dist[t->capat])
                    dist[t->capat] = dist[i] + t->cost;

            t = t->next;

        }
    }

    FILE *f = fopen("dijkstra.out", "w");
    for (i = 2; i <= n; ++i)
        fprintf(f, "%d ", dist[i]);
    fclose(f);
}

int main()
{
    FILE *f = fopen("dijkstra.in", "r");
    fscanf(f, "%d%d", &n, &m);
    int i, j, c;
    for (i = 1; i <= n; ++i)
        v[i] = NULL, dist[i] = INF;

    nod *t;
    for (;m; --m)
    {
        fscanf(f, "%d%d%d", &i, &j, &c);
        t = new nod;
        t->capat = j;
        t->cost = c;
        t->next = v[i];
        v[i] = t;

    }
    fclose(f);
    dijkstra();
/*
    for (i = 1; i <= n; ++i)
    {
        t = v[i];
        printf ("%d ", i);
        while (t != NULL)
        {
            printf ("%d ", t->capat);
            t = t -> next;
        }

        printf ("\n");
    }
*/
    return 0;
}