#include <cstdio>
#include <cstring>

#define INF 200000


int d[1401],fol[1401],sol[1401][1401],n,m,i,j,a,b,c;

void rezolva();

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d %d",&n,&m); 
    
    for (i=1;i<=n;i++)
    	for (j=1;j<=n;j++)
             sol[i][j]=INF;

            
    for (i=1;i<=m;i++) {
	    scanf("%d %d %d",&a,&b,&c);
        sol[a][b]=c; 
    }
	    
    rezolva();
    
    for (i=2;i<=n;i++)
        if (d[i]!=INF)
           printf("%d ",d[i]);
        else
            printf("0 ");
    
    printf("\n");
    
    return 0;
}

void rezolva(){
     int min,nod;

	 memcpy(d,sol[1],sizeof(int)*1101);
	  
     fol[1]=1;
     
     while(1) {
              
		   min=INF;
		   
           for ( i = 1 ; i <= n ; i++ )
		       if ( d[i]<min && !fol[i] ) {
                    min = d[i];
                    nod = i;
		       }
     
           
		   if (min == INF)
		      break;
		      
		   fol[nod]=1;
           for (i = 1 ; i <= n ; i++ )
                if (d[i] > d[nod] + sol[nod][i] ) 
	                d[i] = d[nod] + sol[nod][i];
     }
}