#include<stdio.h>

#define dim 5001

int a[dim][dim],m,n,i,k,b[dim],s[dim],t[dim],x,y;

void read()
{
     scanf("%d%d",&n,&m);
     for(i=1;i<=m;i++)
     scanf("%d%d",&x,&y),scanf("%d",&a[x][y]);
     
}
 
void solve()
{
     for(i=1;i<=n;i++)
     b[i]=a[1][i];
     for(k=1;k<=n;k++)
     t[i]=a[1][i];
     s[1]=1;
     for(k=1;k<=n;k++)
{
     int o;
     int min=dim;
     for(i=1;i<=n;i++)
                      if(a[1][i]<min && a[1][i]!=0 && s[i]==0)
                                      min=a[1][i],o=i;
                                                      s[o]=1;
     for(i=1;i<=n;i++)
                      if(a[o][i]!=0 && a[o][i]+min<a[1][i] || a[1][i]==0 && i!=1 && a[o][i]!=0)
                                    a[1][i]=a[o][i]+min, t[i]=o;
     
     }
     for(i=2;i<=n;i++)
     printf("%d ",a[1][i]);

}
int main ()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read();
    solve();
    return 0;
}