#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[250005];

int main()
{
    int i,j,k,L;
    FILE *f=fopen("dijksta.in","r");
    FILE *g=fopen("dijksta.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(!v[i])
            {
                if(a[c[in].N][i]>0)
                {
                    sf++;
                    c[sf].N=i;
                    c[sf].C=c[in].C+a[c[in].N][i];
                    MN[i]=min(MN[i],c[sf].C);
                }
            }
        }
        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;
}