#include <stdio.h>
FILE*fin,*fout;
int n,i,j,d[1001],an[1001],viz[1001],ok,a[1001][1001],min,m,k,x;

int main()
{
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(k=1; k<=m; k++)
    {
        fscanf(fin,"%d %d %d",&i,&j,&x);
a[i][j]=x;
    }
    for(i=2; i<=n; i++)
    {
      d[i]=1000000002;
	  viz[i]=0;
	  an[i]=-1;
    }
    k=1;
    
    ok=1;
d[1]=0;
    while(ok==1)
    {
        min=1000000001;
        for(i=1; i<=n; i++)
        {
            if(viz[i]==0 && min>d[i])
            {
                min=d[i];
                k=i;
            }
        }

        if(min!=1000000001)
        {
            viz[k]=1;
            for(i=1; i<=n; i++)
            {
                if(viz[i]==0&&d[i]>a[k][i]+d[k]&&a[k][i]!=0)
                {
                    d[i]=a[k][i]+d[k];
                    an[i]=k;
                }
            }
        }
        else{ok=0;break;}

    }

for(i=2;i<=n;i++){
fprintf(fout,"%d ",d[i]);
}
    return 0;
}