#include <cstdio>
#include <cstring>
#include <cstdlib>
#define INF 2000000000


long d[1101],fol[1101],sol[1101][1101],n,m,i,j,a,b,c;

void rezolva();

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%ld %ld",&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("%ld %ld %ld",&a,&b,&c),sol[a][b]=c;
	    
    rezolva();
    
    for (i=2;i<=n;i++)
        if (d[i]!=INF)
           printf("%ld ",d[i]);
        else
            printf("0 ");
    
    system("pause");
    return 0;
}

void rezolva(){
     long min,nod;

	 memcpy(d,sol[1],sizeof(long)*1101); // se poate face asa copierea ...

	  
     fol[1]=1;
     
     while(1) {
              
		   min=INF;
		   
           for ( i = 1 ; i <= n ; i++ )
		       if ( d[i]<min && !fol[i] ) {  // aici .. de unde extragi tu minimele  ?? 
                    min = sol[c][i];
                    nod = i;
		       }
     
           
		   if (min == INF)
		      break;
		      
		   fol[nod]=1;
           for (i = 1 ; i <= n ; i++ ) // aici plecai de la 0 .. dar tu faci matrice de la 1 ...
                if (!fol[i] && d[i]> d[nod] + sol[nod][i] ) // aici trebuia sa verifica daca nodul nu a mai fost fololosit
	                d[i] = d[nod] + sol[nod][i];
     }
}