#include <iostream>  // std
#include <fstream>   // ifstream, ofstream
#include <cassert>   // assert
#include <stdlib.h>  // RAND_MAX

using namespace std;

#define INF RAND_MAX

int main()
{
   int N;
   int M;
   int i,j,w;
   int path;
   
   //--------------------------------------------------------------------------
   // input
   ifstream input("input.txt");
   assert(input);
   input >> N >> M;
   int matrix[N][N];
   for(i=0; i<N; i++)
      for(j=0; j<N; j++)
         matrix[i][j] = 0;
   for(int m=0; m<M; m++)
   {
      input >> i >> j >> w;
      matrix[i][j] = w;
   }
   input.close();
   
   //--------------------------------------------------------------------------         
   int shortPath[2][N];
   for(i=0; i<N; i++)
   {
      shortPath[0][i] = INF;
      shortPath[1][i] = INF;
   }
   shortPath[0][0] = 0; // prima riga dell'output (costo minimo per raggiungere il nodo i da 0)
   shortPath[1][0] = 0; // seconda riga dell'output (nodo padre in un qualche albero minimo)
   
   // scansione per riga
   for(i=0; i<N; i++)
   {
      for(j=0; j<N; j++)
      {
         w = matrix[i][j]; // peso del link
         if(w>0) // se il link esiste...
         {
            path = w+shortPath[0][i]; // ... calcolo il costo del path
            if(path<shortPath[0][j]) // se il path è minore di quello attuale...
            {
               shortPath[0][j] = path; // ... aggiorno l'output
               shortPath[1][j] = i;
            }
         }
      }
   }
   
   //--------------------------------------------------------------------------      
   int trees[N];
   for(i=0; i<N; i++)
      trees[i] = 0;
   
   // scansione per colonna
   for(j=0; j<N; j++)
   {
      for(i=0; i<N; i++)
      {
         w = matrix[i][j];
         path = w+shortPath[0][i];
         // come sopra, ma se il path è papabile, incremento il counter degli alberi
         if(w>0 && path == shortPath[0][j])
            trees[j]++;
      }
   }
   
   int nTrees = 1;
   for(i=1; i<N; i++)
      nTrees *= trees[i];
   
   //--------------------------------------------------------------------------
   // output
   ofstream output("output.txt");
   assert(output);
   for(i=1; i<N; i++)
      output << shortPath[0][i] << " ";
   output << endl;
   for(i=1; i<N; i++)
      output << shortPath[1][i] << " ";
   output << endl;
   output << nTrees << endl;
   output.close();

   return 0;
}