#include <stdio.h>
#include <stdlib.h>
#define MAX 1<<30

typedef struct _Node
{
    int nod,length;
    struct _Node *next;
}Node;
Node *p[250005];

typedef struct _Heap
{
    int nod,cost;
}Heap;

Heap H[50005];
int n,poz_in_heap[50005];

int father(int nod)
{
    return nod/2;
}

int left_son(int nod)
{
    return nod*2;
}

int right_son(int nod)
{
    return nod*2+1;
}

void sift(int nod)
{
    Heap aux;
    int son;
    do
    {
        son=0;
        if(left_son(nod)<=H[0].nod)
            son=left_son(nod);
        if(right_son(nod)<=H[0].nod && H[left_son(nod)].cost>H[right_son(nod)].cost)
            son=right_son(nod);
        if(H[son].cost>H[nod].cost)
            son=0;
        if(son)
        {
            poz_in_heap[H[son].nod]=nod;
            poz_in_heap[H[nod].nod]=son;

            aux=H[son];
            H[son]=H[nod];
            H[nod]=aux;
            nod = son;
        }
    }while(son);
}

void percolate(int nod)
{
    Heap aux;
    int key=H[nod].cost;
    while((nod>1) && (key<H[father(nod)].cost))
    {
        poz_in_heap[H[father(nod)].nod]=nod;
        poz_in_heap[H[nod].nod]=father(nod);

        aux=H[nod];
        H[nod]=H[father(nod)];
        H[father(nod)]=aux;
    }
}


void cut(int nod)
{
    H[nod]=H[H[0].nod];
    poz_in_heap[nod]=H[0].nod;
    poz_in_heap[H[H[0].nod].nod]=nod;
    H[0].nod--;
    if((nod>1) && H[nod].cost<H[father(nod)].cost)
        percolate(nod);
    sift(nod);
}

void insert(int value,int nod)
{
    H[++H[0].nod].cost=value;
    H[H[0].nod].nod=nod;
    poz_in_heap[nod]=H[0].nod;
    percolate(H[0].nod);
}

void adaugare_dupa(Node *p, int valoare, int length)
{
    Node *q=(Node*)malloc(sizeof(Node));
    q->next=p->next;
    q->nod=valoare;
    q->length=length;
    p->next=q;
}

void Dijkstra(int n, FILE *g)
{
    int i,poz_curenta=1,cost[50005],vizitat[50005];
    for(i=2;i<=n;i++)
    {
        vizitat[i]=0;
        cost[i]=MAX;
        poz_in_heap[i]=0;
        H[i].nod=0;
        H[i].cost=MAX;
    }
    cost[1]=0;
    vizitat[1]=1;
    poz_in_heap[1]=1;
    H[1].cost=0;
    H[1].nod=1;
    Node *q;
    for(i=1;i<=n;i++)
    {
        q=p[poz_curenta]->next;
        while(q!=p[poz_curenta])
        {
            if(!vizitat[q->nod])
            {
                insert(q->length+cost[poz_curenta],q->nod);
                if(cost[poz_curenta] + q->length < cost[q->nod])
                    cost[q->nod]=q->length+cost[poz_curenta];
                vizitat[q->nod]=1;
            }
            else if(cost[poz_curenta] + q->length < cost[q->nod])
            {
                H[poz_in_heap[q->nod]].cost =  cost[poz_curenta] + q->length;
                cost[q->nod]=H[poz_in_heap[q->nod]].cost;
                percolate(poz_in_heap[q->nod]);
            }
            q=q->next;
        }
        poz_curenta=H[1].nod;
        cut(1);
    }
    for(i=2; i <= n; i++)
    {
        if(cost[i]==MAX)
            fprintf(g, "0 ");
        else fprintf(g, "%d ", cost[i]);
    }
}
int main()
{
    FILE *f=fopen("dijkstra.in", "r");
    FILE *g=fopen("dijkstra.out", "w");
    int n,m,x,y,i,length;
    fscanf(f,"%d %d", &n, &m);
    for(i=1;i<=n;i++)
    {
        p[i]=(Node*)malloc(sizeof(Node));
        p[i]->next=p[i];
        p[i]->nod=0;
    }
    for(i=0;i<m;i++)
    {
        fscanf(f,"%d%d%d", &x ,&y, &length);
        adaugare_dupa(p[x],y, length);
    }
    Dijkstra(n,g);
    return 0;
}