#include <iostream>
#include <fstream>

using namespace std;

int n,m,MN[50005];
short a[5000][5000];
bool v[50005];

struct coada{
int N,C;
};
coada c[500005];

int main()
{
    int i,j,k,L;
    FILE *f=fopen("dijkstra.in","r");
    FILE *g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            a[i][j]=-1;
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&j,&k,&L);
        a[j][k]=L;
    }
    for(i=1;i<=n;i++)
        MN[i]=2<<30-1;
    c[1].N=1;
    v[1]=true;
    int in=1,sf=1;
    while(in<=sf)
    {
        for(i=1;i<=n;i++)
        {
            if(a[c[in].N][i]>0)
            {
                if(!v[i])
                {
                    sf++;
                    c[sf].N=i;
                    c[sf].C=c[in].C+a[c[in].N][i];
                    MN[i]=min(MN[i],c[sf].C);
                    v[i]=true;
                }
                else if(MN[i]>(c[in].C+a[c[in].N][i]))
                {
                    MN[i]=c[in].C+a[c[in].N][i];
                    sf++;
                    c[sf].N=i;
                    c[sf].C=MN[i];
                }
            }
        }
        in++;
    }
    for(i=2;i<=n;i++)
    {
        if(MN[i]!=2<<30-1)
            fprintf(g,"%d ",MN[i]);
        else fprintf(g,"%d ",0);
    }
    fprintf(g,"\n");
    return 0;
}