#include<stdio.h>
using namespace std;
int a[100][100]; int b[10000];
bool pas[10000],viz[10000];
int vfp; int x,y,cost; int maxim=0;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,i,j,vf,vfp; int k,p,u,minim,nou; int ok;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&cost);a[x][y]=cost;if(cost>maxim)maxim=cost;}maxim+=100;
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]==0){a[i][j]=maxim;}
    vfp=1;
    b[1]=vfp;p=1;u=1;k=0;
    minim=maxim;                  viz[vfp]=1;

    while(k<n)
    {
        while(p<=u)
        {
            vf=b[p];
            if(pas[vf]==0)
            {
                for(i=1;i<=n;i++)
                    if(viz[i]==0)
                    {
                        ok=1;
                        if(a[vf][i]<minim){minim=a[vf][i];nou=i;}
                    }
                if(ok==0)pas[vf]=1;
            }
            p++;
        }
        p=1;minim=maxim;
        u++;b[u]=nou;viz[nou]=1;k++;
        for(i=1;i<=n;i++)
            if(i!=vfp&&i!=nou)
                if(a[vfp][i]>a[vfp][nou]+a[nou][i])
                    a[vfp][i]=a[vfp][nou]+a[nou][i];
    }
    for(i=2;i<=n;i++)printf("%d ",a[1][i]);
    return 0;
}