#include <stdio.h>
#include <stdlib.h>
#define MAX 1<<30
typedef struct _Node
{
    int nod,length;
    struct _Node *next;
}Node;
Node *p[100001];
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 show(Node *p, FILE *g)
{
    Node *q=p->next;
    if(q==p)
        fprintf(g,"0\n");
        else
        {
            while(q!=p)
            {
                fprintf(g,"(%d : %d) ", q->nod, q->length);
                q=q->next;
            }
        fprintf(g,"\n");
        }
}

void Dijkstra(int n, FILE *g)
{
    int ok=0,i,vizitat[50001],poz_curenta=1,j,min;
    int cost[50001];
    for(i=1;i<=n;i++)
    {
        cost[i]=MAX;
        vizitat[i]=0;
    }
    cost[1]=0;
    Node *q;
    for(j=1;j<=n;j++)
    {
        min=MAX;
        q=p[poz_curenta]->next;
        vizitat[poz_curenta]=1;
        while(q!=p[poz_curenta])
        {
            if(cost[poz_curenta]+q->length<cost[q->nod])
                cost[q->nod]=cost[poz_curenta]+q->length;
            q=q->next;
        }
        for(i=1;i<=n;i++)
            if(!vizitat[i] && cost[i]<min)
            {
                min=cost[i];
                poz_curenta=i;
            }
    }
    for(i=2;i<=n;i++)
    {
        if(cost[i]==MAX)
            cost[i]=0;
        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);
   // for(i=1;i<=n;i++)
        //show(p[i],g);
    return 0;
}