#include <stdio.h>
#include <stdlib.h>

struct edge {
  int source;
  int target;
  int weight;
};

/* A graph is an array of edges. */
typedef struct edge* graph;

int kruskal_mst(graph g, int num_edges, int num_vertices, graph tree);

int main(int argc, char* argv[]) {
  int num_edges, num_vertices, i, num_edges_in_tree;
  graph g;
  FILE* f;
  graph tree;

  f = fopen(argv[1], "r");

  /* Read in the number of edges from the file */
  fscanf(f, "%d\n", &num_edges);

  /* Read in the number of vertices from the file */
  fscanf(f, "%d\n", &num_vertices);

  /* Read the graph from the file */
  g = (graph)malloc(num_edges * sizeof(struct edge));
  for (i = 0; i != num_edges; ++i)
    fscanf(f, "%d-%d-%d\n", &g[i].source, &g[i].weight, &g[i].target);

  /* allocate memory for the tree */
  tree = (graph)malloc(num_vertices * sizeof(struct edge));

  /* Find the minimum spanning tree using Kruskal's algorithm */
  num_edges_in_tree = kruskal_mst(g, num_edges, num_vertices, tree);

  /* Print out the minimum spanning tree */
  printf("%d\n", num_edges_in_tree);
  printf("%d\n", num_vertices);
  for (i = 0; i != num_edges_in_tree; ++i)
    printf("%d-%d-%d\n", tree[i].source, tree[i].weight, tree[i].target);
  
  return 0;
}