#include <stdio.h>

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

const int inf = 500000000;
int m, n, heap_size = 0;
plist *vecini;
int *sel, *drum, *heap, *poz;

void init();
void dijkstra();
void write();
void push(int);
void pop(int);
void move_up(int);
void move_down(int);
inline void swap(int&, int&);

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

void dijkstra()
{
    int k;
    plist p;
    while (heap_size)
    {
        k = heap[1];
        pop(1);

        for (p = vecini[k]; p; p = p->next)
        {
            if (drum[p->nod] > drum[k] + p->val)
            {
                if (sel[p->nod])
                {
                    move_up(poz[p->nod]);
                }
                else
                {
                    drum[p->nod] = drum[k] + p->val;
                    push(p->nod);
                }
            }
        }
    }
}

void pop(int x)
{
    sel[heap[x]] = 0;
    heap[x] = heap[heap_size];
    poz[heap[x]] = x;
    --heap_size;
    move_down(x);
}

void move_down(int tata)
{
    int fiu;
    for (fiu = tata * 2; fiu <= heap_size; fiu = fiu * 2)
    {
        if (fiu < heap_size)
        {
            if (drum[heap[fiu+1]] < drum[heap[fiu]])
            {
                fiu++;
            }
        }
        if (drum[heap[tata]] <= drum[heap[fiu]])
        {
            return;
        }
        swap(heap[tata], heap[fiu]);
        swap(poz[heap[tata]], poz[heap[fiu]]);
        tata = fiu;
    }
}

void push(int x)
{
    heap[++heap_size] = x;
    poz[x] = heap_size;
    sel[x] = 1;
    move_up(heap_size);
}

void move_up(int fiu)
{
    int tata =  fiu / 2;
    while (fiu > 1 && drum[heap[fiu]] < drum[heap[tata]])
    {
        swap (heap[fiu], heap[tata]);
        swap (poz[heap[fiu]], poz[heap[tata]]);
        fiu = tata;
        tata = fiu / 2;
    }
}

void init()
{
    int i, x, y, z;
    plist p;
    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);
        p = new list;
        p->nod = y;
        p->val = z;
        p->next = vecini[x];
        vecini[x] = p;
    }
    fclose (fin);
    sel = new int[n+1];
    drum = new int[n+1];
    heap = new int[n+1];
    poz = new int[n+1];
    for (i = 1; i <= n; ++i)
    {
        sel[i] = 0;
        drum[i] = inf;
    }
    drum[1] = 0;
    for (p = vecini[1]; p; p = p->next)
    {
        drum[p->nod] = p->val;
        push(p->nod);
    }
}

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

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