#include <cstdio>
#include <cstring>

#define INF 20000000


unsigned d[1101],fol[1101],sol[1101][1101],n,m,i,j,a,b,c; // tipul .. de date .. ca sa incapa ..unsigned

void rezolva();

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%ud %ud",&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("%ud %ud %ud",&a,&b,&c),sol[a][b]=c; // nu scrie in sursa ca daca ai muchie de la "a" la "b"
	    // e si de la "b" la "a" ....
	    
    rezolva();
    
    for (i=2;i<=n;i++)
        if (d[i]!=INF)
           printf("%ud ",d[i]);
        else
            printf("0 "); // aici cand afisai .. uitai sa pui spatiu dupa 
    
    printf("\n"); // ai uitat sa treci la linie noua la sf
    
    return 0;
}

void rezolva(){
     unsigned min,nod;

	 memcpy(d,sol[1],sizeof(int)*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 = d[i]; // si aici ...
                    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 (d[i] > d[nod] + sol[nod][i] ) 
	                d[i] = d[nod] + sol[nod][i];
     }
}