#include <stdio.h>

#define MAX 50002
#define INF 999999

typedef struct nodS {
    int nod;
    int cost;
    nodS* next;
} NOD, *PNOD;

int n, m, source;
PNOD a[MAX];
int d[MAX], poz[MAX], h[MAX], hsize;
bool not_in_heap[MAX];

void add(PNOD& p, int nod, int val);
void dijkstra();
void build_heap();
void rebuild_heap(int nod);
void move_up(int nod);
int extract_min();

int main()
{
    int nod1, nod2, cost;
    FILE *fin = fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        fscanf(fin, "%d%d%d", &nod1, &nod2, &cost);
        add(a[nod1], nod2, cost);
    }
    fclose(fin);
    
    dijkstra();
    
    FILE *fout = fopen("dijkstra.out", "w");
    for (int i = 2; i <= n; ++i)
        fprintf(fout, "%d ", d[i]);
    fclose(fout);
    
    return 0;
}

void dijkstra()
{
    int curr;
    source = 1;
    build_heap();
    while (hsize)
    {
         curr = extract_min();
         not_in_heap[curr] = true;
         for (PNOD p = a[curr]; p; p = p->next)
             if (d[p->nod] > d[curr] + p->cost)
             {
                 d[p->nod] = d[curr] + p->cost;
                 if (not_in_heap[p->nod])
                 {
                      h[++hsize] = p->nod;
                      poz[p->nod] = hsize;
                      not_in_heap[p->nod] = false;
                      move_up(p->nod);
                 }
                 else
                     move_up(p->nod);
             }
    }
}

void build_heap()
{
    for (int i = 1; i <= n; ++i)
    {
        h[i] = i;
        poz[i] = i;
        d[i] = INF;
    }
    d[source] = 0;
    hsize = n;
    for (int i = n/2; i > 0; --i)
        rebuild_heap(i);
}

void rebuild_heap(int nod)
{
    int value = h[nod];
    int parent = nod;
    int son = 2*nod;
    while (son <= hsize)
    {
        if (son < hsize)
            if (d[ h[son] ] > d[ h[son+1] ])
                son++;
        if (d[value] > d[ h[son] ])
        {
            h[parent] = h[son];
            poz[h[parent]] = parent;
            parent = son;
            son = 2*parent;
        }
        else
            break;
    }
    h[parent] = value;
    poz[h[parent]] = parent;
}

void move_up(int nod)
{
    int value = h[poz[nod]];
    int son = poz[nod];
    int parent = son / 2;
    while (parent && d[ h[parent] ] > d[ value ])
    {
        h[son] = h[parent];
        poz[h[son]] = son;
        son = parent;
        parent /= 2;
    }
    h[son] = nod;
    poz[h[son]] = son;
}

int extract_min()
{
    int aux;
    aux = h[1];
    h[1] = h[hsize];
    h[hsize] = 0;
    hsize--;
    rebuild_heap(1);
    return aux;
}

void add(PNOD& p, int nod, int val)
{
    if (!p)
    {
        p = new NOD;
        p->nod = nod;
        p->cost = val;
        p->next = 0;
    }
    else
    {
        PNOD paux =new NOD;
        paux->nod = nod;
        paux->cost = val;
        paux->next = p;
        p = paux;
    }
}