import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main {
	 static ArrayList<Pair <Integer, Pair<Integer, Integer> >> adj;
	 static int[] rank ;
	 static int[] set;
	 static ArrayList< Pair<Integer, Integer >> sol;
	 
	static int findSet (int x) {
		int y = x;
		while (set[y] != y)
			y = set[y];
		int res = y;
		y =x;
		while (set[y] != y){
			set[y] = res;
			y = set[y];
		}
		return res;
	}
	
	static void union (int u, int v) {
		if (rank[u] > rank[v]){
			set[v] = u;
			return;
		}
		if (rank[u] < rank[v]){
			set[u] = v;
			return;
		}
		set[u] = v;
		rank[v]++;		
		
	}

	 
	public static void main(String[] args) throws IOException {
		 BufferedReader bf = new BufferedReader(new FileReader("apm.in"));
		 //PrintStream out = new PrintStream();
		 OutputStream out = new BufferedOutputStream ( new FileOutputStream("apm.out") );
	     String tmp[] = bf.readLine().split(" ");
	     int n = Integer.parseInt(tmp[0]);
	     int m = Integer.parseInt(tmp[1]);
	      
		 adj = new ArrayList<Pair< Integer, Pair<Integer, Integer>>>();
		 sol = new ArrayList<Pair<Integer, Integer>>();
		 set = new int[n+1];
		 rank = new int[n+1];
		 for(int i = 1; i <= n; i++) {
			 set[i] = i;
			 rank[i] = 1;
		 }
		 
	     for (int i = 0; i < m; i++) {
           tmp = bf.readLine().split(" ");
           int x = Integer.parseInt(tmp[0]);
           int y = Integer.parseInt(tmp[1]);
           int cost = Integer.parseInt(tmp[2]);
           adj.add(new Pair(x,new Pair(y, cost)));
           adj.add(new Pair(x,new Pair(y, cost)));
	     }
		 
		 Comparator<Pair<Integer, Pair<Integer, Integer>>> c = new Comparator<Pair<Integer, Pair<Integer, Integer>>>() {
			 @Override
				public int compare(Pair<Integer, Pair<Integer, Integer>> o1, Pair<Integer, Pair<Integer, Integer>> o2) {
					return o1.y.y - o2.y.y;
				}
		};
		
		 Collections.sort(adj, c);
		 int cost = 0;
		 for (int i = 0 ;i < adj.size() ; i++){
			 if (sol.size() == n - 1 )
				 break;
			 Pair<Integer, Pair<Integer, Integer>> x = adj.get(i);
			 int p1 = findSet(x.x);
			 int p2 = findSet(x.y.x);
			 if ( p1 != p2 ){
				 sol.add(new Pair(x.x, x.y.x));
				 union(p1, p2);
				 cost +=  x.y.y;
			 }	 
			 
		 }
		 
		 out.write((cost + "\n").getBytes());
		 out.write((n - 1 + "\n").getBytes());
		 for (int i = 0 ; i < sol.size() ; i++)
			  out.write((sol.get(i).x + " " + sol.get(i).y + "\n").getBytes());
		 out.flush();
		 out.close();
		 bf.close();
		 
	}
}
		
class Pair <A,B>{
	A x;
	B y;
	public Pair(A x, B y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}