import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
class Main{
	static class Edge{
		int u;
		int v;
		int w;
		public Edge(int u, int v, int w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public String toString() {
			return "(" + u + ", " + v + ", " + w +")"; 
		}
	}
	static List<Edge> edges;
	static List<Edge> ama;
	static int idC[];
	static int N;
	static int M;
	static long cost = 0;
	static int countEdges = 0;
	public static void kruskal() {
		ama  = new ArrayList<>();
		for (int i = 1; i < N; i++) 
			idC[i] = i;
		
		Collections.sort(edges, new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.w - o2.w;
			}
		});
		
		for (Edge e : edges) {
			if(idC[e.u] != idC[e.v]) {
				ama.add(e);
				union(idC[e.u], idC[e.v]);
				cost += e.w;
				countEdges++;
			}
		}
	}
	
	static void union(int u, int v) {
		for (int i = 1; i < N + 1; i++)
			if (idC[i] == u) {
				idC[i] = v;
			}
	}

	
	public static void main(String[] args) throws IOException {
		Scanner input = new Scanner(new FileReader("apm.in"));
		N = input.nextInt();
		M = input.nextInt();
		idC = new int[N + 1];
		edges = new ArrayList<>();
		int u, v, w;
		for (int i = 0; i < M; i++) {
			u = input.nextInt();
			v = input.nextInt();
			w = input.nextInt();
			edges.add(new Edge(u, v, w));
		}
		input.close();
		
		kruskal();
		PrintWriter output = new PrintWriter("apm.out");
		output.println(cost);
		output.println(countEdges);
		
		for(Edge e : ama) {
			output.println(e.u + " " + e.v);
		}
		output.close();
	   
	}
}