#include <stdio.h>

typedef struct list
{
    int nod, val;
    list *next;
} *plist;

const int INF = 1000000000;
int m, n;
int *tati, *drum, *sel;
plist *vecini;

void read();
void add(int, int, int);
void write();
void dijkstra();

int main()
{
    read();
    dijkstra();
    write();
    return 0;
}

void dijkstra()
{
    int k = 1, min, i;
    plist p;
    drum[k] = 0;
    while (1)
    {
        sel[k] = 1;
        for (p = vecini[k]; p; p = p->next)
        {
            if (drum[p->nod] > drum[k] + p->val)  //pot imbunatati: mai pun conditie !sel[p->nod]
            {
                drum[p->nod] = drum[k] + p->val;
                tati[p->nod] = k;
            }
        }

        min = INF;

        for (i = 1; i <= n; ++i)
        {
            if (!sel[i] && drum[i] < min)
            {
                min = drum[i];
                k = i;
            }
        }
        if (min == INF)
        {
            break;
        }
    }
}

void write()
{
    int i;
    FILE *fout = fopen ("dijkstra.out", "w");
    for (i = 2; i <= n; ++i)
    {
        fprintf (fout, "%d ", drum[i]);
    }
    fclose (fout);
}

void read()
{
    int i, x, y, z;
    FILE *fin = fopen ("dijkstra.in", "r");
    fscanf (fin, "%d%d", &n, &m);
    vecini = new plist[n+1];
    for (i = 1; i <= n; ++i)
    {
        vecini[i] = 0;
    }
    for (i = 1; i <= m; ++i)
    {
        fscanf (fin, "%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    fclose (fin);
    tati = new int[n+1];
    drum = new int[n+1];
    sel = new int[n+1];
    for (i = 1; i <= n; ++i)
    {
        tati[i] = 0;
        drum[i] = INF;
        sel[i] = 0;
    }
}

void add(int source, int dest, int cost)
{
    plist p = new list;
    p->nod = dest;
    p->val = cost;
    p->next = vecini[source];
    vecini[source] = p;
}