#include <stdio.h>
#include <stdlib.h>
# define nmax 50002
# define mmax 250002
# define inf 2000000000
struct muchie
{
    int x,y,c;
} G[mmax];
FILE *f,*fout;
int D[nmax],M,N;
int main()
{
    int i,x,y,c,ok;
    f=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(f," %d %d ",&N,&M );
    for (i=1;i<=M;++i)
        {
            fscanf(f," %d %d %d ",&x,&y,&c );
            G[i].x=x;
            G[i].y=y;
            G[i].c=c;
            if (x==1)
                D[y]=c;
    }
    for (i=2;i<=N;++i)
        if (D[i]==0)
            D[i]=inf;
         do  {
             ok=1;
             for (i=1;i<=M;++i)
                 if (D[G[i].y]>D[G[i].x]+G[i].c)
                     {
                         D[G[i].y]=D[G[i].x]+G[i].c;
                         ok=0;
                         }
         }while (!ok);
         for (i=2;i<=N;++i)
             if (D[i]!=inf)
                 fprintf(fout," %d ",D[i]);
             else
                 fprintf(fout," 0 ");
                 fclose(f);
                 fclose(fout);
             return 0;

}
//Performanta algoritmului este destul de buna,adica 0,06s tinand cont ca programul este facut iterativ si nu recursiv,pentru optiizarea lui putem face un subprogram cu algoritmul lui Dijkstra iar atunci  timpul de executie va fi mai mic