#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>
using namespace std;
#define P 60
#define MAX 1000

int m[P][P];
int v[P][P];
int D[P], G[P][P], W[P][P],Z[P];
int N,M,S,F;
int a,b,c;
int i,j,k,l,h,f;

void GRAF (int m[P][P]) {

   for (i=1 ; i<=N ; i++ )
    D[i] = m[S][i];
    D[S] = 0 ;

   for (j=1; j<=2 ; j++) {
    G[j][1]=S;
    G[S][j]=0;
   }


   for (h=1 ; h<=N ;h++) {
    i=0;
    for (j=2 ; j<=N ; j++) {
     for (k=1 ; k<=N ; k++) {

      if (D[k] > D[j]+m[j][k])
	D[k]=D[j]+m[j][k] ;
	i++;

	for (l=2 ; l<=N ; l++) {
	 W[i][l]=D[l];
	 if (W[i][l]<W[i-1][l])
	  G[k][2]=j ;
	}
     }
    }
   }

    printf("\n");

  if (D[F]<MAX)
    {

    printf("\nlen %d --> %d = ",S,F);
    printf("%d \n",D[F]);

    printf(" %d --> %d : ",S,F);

    i=1;
    Z[0]=F;

    while ( G[F][2] !=0 ) {
     Z[i]=G[F][2];
     i++;
     G[F][2]=G[G[F][2]][2];
    }
     Z[i]=S;

   for (j=i ; j>=0 ;j--)
    printf(" %d",Z[j]);

  }
//     else {
  //    printf("\nError\n\n\n");
    //  return;
     //}

return;

}

void PYTU () {

   while (D[F]<MAX)  {
    GRAF(v);
    for (j=0 ; j<M ; j++)
    v[Z[j+1]][Z[j]]=MAX;
   }

  return;
}


int main () {


    scanf ("%d %d",&N,&M);

   for ( i=1 ; i<=N ; i++)
    for ( j=1 ; j<=N ; j++) {
     m[i][j]=MAX;
     v[i][j]=MAX;
    }

   for (i=1 ;i<=M ;i++ ) {
    scanf("%d %d %d",&a,&b,&c);
       m[a][b]=c;
   //  m[b][a]=1;
       v[a][b]=1;
   }
   for (i=1;i<=M;i++)
   {
       for (k=1;k<=M;k++) { if (m[i][k]!=1000)  printf("%d ",m[i][k]); else  printf("0 ");}
        printf("\n");
   }
     printf("\n");

   printf("Start, end : ");
   scanf ("%d %d",&S,&F);

   PYTU();
   printf("Min : ");
   GRAF(m);

 getch();
 return 0 ;
}