#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <fstream>
 

#include <limits>  //per limiti nuimerici
#include <set>
#include <utility>
#include <algorithm>
#include <iterator>

typedef int vertex_t;
typedef double weight_t;

const weight_t max_weight = std::numeric_limits<double>::infinity();

int n_paths;

struct neighbor {
 vertex_t target;
weight_t weight;
neighbor(vertex_t arg_target, weight_t arg_weight)
: target(arg_target) , weight(arg_weight) { }
};

typedef std::vector<std::vector<neighbor> > adjacency_list_t;

void DijkstraComputePaths(vertex_t source, const adjacency_list_t &adjacency_list, std::vector<weight_t> &min_distance, std::vector<vertex_t> &previous)

{
int n = adjacency_list.size();
min_distance.clear();
min_distance.resize(n,max_weight);
min_distance[source] = 0;
previous.clear();
previous.resize(n, -1);
std::set<std::pair<weight_t, vertex_t> > vertex_queue;

vertex_queue.insert(std::make_pair(min_distance[source], source));

n_paths=0;
while (!vertex_queue.empty())

{
weight_t dist = vertex_queue.begin()->first;
vertex_t u = vertex_queue.begin()->second;

vertex_queue.erase(vertex_queue.begin());


n_paths++;
//visit ogni arc exiting u!!
const std::vector<neighbor> &neighbors = adjacency_list[u];
int tmp=0;

for(std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
neighbor_iter != neighbors.end();
neighbor_iter++)

{

vertex_t v = neighbor_iter->target;
weight_t weight = neighbor_iter->weight;
weight_t distance_through_u = dist + weight;

if (distance_through_u < min_distance[v]) {
n_paths++;

vertex_queue.erase(std::make_pair(min_distance[v], v));

min_distance[v] = distance_through_u;
previous[v] = u;

vertex_queue.insert(std::make_pair(min_distance[v], v));
}

}
}


}


std::vector<vertex_t> DijkstraGetShortestPathTo( vertex_t vertex, const std::vector<vertex_t> &previous){
std::vector<vertex_t> path;
for(; vertex!= -1; vertex = previous[vertex])
path.push_back(vertex);
return path;
}



int main()
{
std::ofstream fout ("output.txt");
std::ifstream fin ("input.txt");

int v, e , k , l, w;
fin >> v >> e;

adjacency_list_t adjacency_list(v);
for(int i=0; i < e; i++){
fin >> k >> l >> w;

adjacency_list[k].push_back(neighbor(l, w));
}


std::vector<weight_t> min_distance;
std::vector<vertex_t> previous;

DijkstraComputePaths(0, adjacency_list, min_distance, previous);

for(int i=1; i< min_distance.size(); i++){
fout << min_distance[i] << "  ";

}
fout << std::endl;
for (int i=1; i < min_distance.size(); i++){
previous.clear();
std::vector<vertex_t> path = DijkstraGetShortestPathTo(i, previous);
fout << path[1] << "  ";

}
fout << std:: endl;
fout << (n_paths-1 + min_distance.size()-1)%1000000 <<std::endl;

return 0;
}