#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cassert>
#include <limits>
#include <vector>

using namespace std;


std::vector< std::vector<int> > graph;  
std::vector< int > pred;
std::vector<int> dist;
std::vector<bool> visitedSet; 


int n,m,u,v,w;

int minDistance()
{
  /* finding minimum distance in all the unexplored nodes */
  int min = std::numeric_limits<int>::max(), min_index = 0;

  for(int v = 0; v < n; ++v)
    {
      if(visitedSet[v] == false && dist[v] <= min)
	{
	  min = dist[v];
	  min_index = v;
	} 
    }
  return min_index;
}

int shortestPath(int source)
{

  for(int i = 0; i < n; ++i)
    {
      dist[i] = std::numeric_limits<int>::max(); // infinite distance
      visitedSet[i] = false;
    }

  /*source distance from itself is 0*/
  dist[source] = 0;

  /*for each node in graph*/
  for(int c = 0; c < n; ++c)
    {
      int u = minDistance();
      visitedSet[u] = true;
      
      /*for each node in the proximity list of u*/
      for(int v = 0; v < n; ++v)
	{
	  if(!visitedSet[v] && graph[u][v] && dist[u] != std::numeric_limits<int>::max() && dist[u]+graph[u][v] < dist[v])
	    {
	      dist[v] = dist[u] + graph[u][v];
	      pred[v] = u; //keeping predecessor's trace
	    }
	}
    }
  return 0;
}

int main(int argc, char **argv)
{

  std::ifstream input("input.txt");
  std::ofstream output("output.txt");

  assert(input);
  assert(output);

  input >> n >> m;

  graph.resize(n);

  for(int i = 0; i < n; ++i)
    {
      graph[i].resize(n);
    }

  //result.resize(n);

  dist.resize(n);
  visitedSet.resize(n);
  pred.resize(n);

  /*populating graph*/
  for(int i = 0; i < m; ++i)
    {
      input >> u >> v >> w;
      graph[u][v] = w;
    }
  /*computing Dijkstra's solution from node 0*/
  shortestPath(0);

  /*generating output*/
  for(int i = 1; i < n; ++i)
    output << dist[i] << " ";

  output << std::endl;
  for(int i = 1; i < n; ++i)
    output << pred[i] << " ";

  output << std::endl;

  input.close();
  output.close();

}