#include<stdio.h>
using namespace std;
bool viz[50001]; int dist[50001],a[1000][1000];
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,i,j,maxim=50000001,minim=0;
    scanf("%d%d",&n,&m);
    //initializari_______________________________
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=-1;
    for(i=1;i<=n;i++)dist[i]=maxim;

    int x,y,cost,vfp=1;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&cost);
        a[x][y]=cost;
        if(x==vfp)dist[y]=cost;
    }

    int k=1,vf; viz[vfp]=1;
    while(k<=n)
    {
        minim=maxim;
        for(i=1;i<=n;i++)if(viz[i]==0)if(dist[i]<minim){minim=dist[i];vf=i;}
        viz[vf]=1;k++;
        for(i=1;i<=n;i++)if(viz[i]==0&&a[vf][i]!=-1)if(dist[i]>dist[vf]+a[vf][i])dist[i]=dist[vf]+a[vf][i];
    }

    for(i=2;i<=n;i++)if(dist[i]==maxim)printf("0 "); else printf("%d ",dist[i]);
    return 0;
}