#include<stdio.h>
#define NMaxVf 50
#define Inf 32000;

int n,x0;
int C[NMaxVf][NMaxVf];
int M[NMaxVf],pre[NMaxVf];
int d[NMaxVf];

void Citire();
void Afisare();

int main(){
    int i,VfMin,j;
    double dMin;
    Citire();
    for (j=1;j<n;j++)
	{dMin=Inf;
	for (i=1;i<=n;i++)
	    if (!M[i] && dMin>d[i]){
	       dMin=d[i];
	       VfMin=i;
	    }
	M[VfMin]=1;
	for (i=1;i<=n;i++)
	    if (!M[i]&& d[i]>dMin+C[VfMin][i])
	       {pre[i]=VfMin;
		d[i]=dMin+C[VfMin][i];}
    }
    Afisare();
    return 0;
}

void Citire(){
     int i,j,m,x,y;
     int c;
     freopen("dijkstra.in","r",stdin);
     scanf("%d %d",&n,&m);
     for (i=1;i<=n;i++)
	 for (j=i+1;j<=n;j++)
	     C[i][j]=C[j][i]=Inf;
     for (i=1;i<=m;i++){
         scanf("%d %d %d",&x,&y,&c);
         C[x][y]=c;
     } 
     for (i=1;i<=n;i++){ d[i]=C[1][i];pre[i]=1; }
     M[1]=1;pre[1]=0;
}

void Afisare(){
int i,j, lg, dr[NMaxVf];
     freopen("dijkstra.out","w",stdout);
     for (i=2;i<=n;i++){
         printf("costul este:%d \n",d[i]);
         dr[0]=i;lg=0;
         while (pre[dr[lg]]){
               lg++;dr[lg]=pre[dr[lg-1]];
         }
         for (j=lg;j>=0;j--) printf("%d",dr[j]);
         printf("\n");
     }
}