#include <stdio.h>
#define nmax 10000
#define inf 32000

int i,j,min,x,y,ct,n,m;
int c[nmax][nmax],d[nmax],viz[nmax],p[nmax];

int main()
{
 freopen("dijkstra.in","r",stdin);   
 freopen("dijkstra.out","w",stdout);   
    
 for(i=1;i<=n;i++)
    {
     for(j=1;j<=n;j++)
       c[i][j]=inf;
     c[i][i]=0;
     }
 for(i=1;i<=m;i++)
    {
     scanf("%d %d %d", &x, &y, &ct);
     c[x][y]=ct;
     }
     
 
 for(i=1;i<=n;i++)
     if(i!=1)             
             d[i]=c[1][i];
                
 viz[1]=1;
                
 for(j=1;j<n;j++)                 
   {
      min=inf;
      for(i=1;i<=n;i++)
         if(viz[i]==0 && min>d[i])
              {
               min=d[i];
               y=i;
               }        
      
      
    viz[y]=1;
  
    for(i=1;i<=n;i++)
     if(viz[i]==0 && d[i]>min+c[y][i])
         d[i]=min+c[y][i];
   }     
 
 for(i=2;i<=n;i++)
    printf("%d ", d[i]); 
 
 return 0;
}