#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;


class Edge{
private:
     int nodeA,nodeB,cost;
public:
     Edge(int x,int y,int c){
          nodeA = x;
          nodeB = y;
          cost = c;
     }
     int* get_cost(){
          return &cost;
     }
     pair<int,int> getNodes(){
          return pair<int,int>(nodeA,nodeB);
     }
};

class disjointSet{
private:
     const static int limit = 200001;
     int group[limit];
     int height[limit];
public:
     disjointSet(){};
     void init_disjoint_set(int n){
          for(int i = 1; i <= n; i++){
	group[i] =i;
	height[i] =0;
          }
     }
     int find_group(int x){
          if(x == group[x])
	return x;
          return group[x] = find_group(group[x]);
     }
     void unite(int x,int y){
          if(x == y)
	return;
          int xRoot = find_group(x);
          int yRoot = find_group(y);
          if(height[xRoot] < height[yRoot])
	group[xRoot] = yRoot;
          else if(height[xRoot] > height[yRoot])
	group[yRoot] = xRoot;
          else{
	group[yRoot] = xRoot;
	height[xRoot]++;
          }
     }
     bool is_same_set(int x,int y){
          return find_group(x) == find_group(y);
     }
};

class Graph{
private:
     vector<Edge> v;
     disjointSet someSet;
     vector<int> mst_indexes;
     int mst_cost = 0;
     int nodes,edges;
     struct myCompare{
          bool operator()(Edge a, Edge b){
	return *a.get_cost() < *b.get_cost();
          } 
     }cost_compare;
     bool forms_cycle(Edge a){
          
     }
public:
     Graph(int n,int m){
          edges =m;
          nodes =n;
          someSet.init_disjoint_set(n);
     }
     void insert_edge(Edge x){
          v.push_back(x);
     }
     Edge* get_edge(int index){
          return &v[index];
     }
     vector<Edge>* get_collection_edges(){
          return &v;
     }
     void sort_edges_after_cost(){
          sort(v.begin(),v.end(),cost_compare);
     }
     void print_edges(){
          for(int i = 0; i < v.size(); i++){
	pair<int,int> nodes = v[i].getNodes();
	cout << nodes.first << " " << nodes.second << " " << *(v[i].get_cost())<< endl;
          }
     }
     void compute_mst(){
          mst_indexes.push_back(0);
          someSet.unite(v[0].getNodes().first,v[0].getNodes().second);
          mst_cost+=*v[0].get_cost();
          for(int i = 1 ;i < v.size(); i++){
	pair<int,int> nodes = v[i].getNodes();
	int groupX = someSet.find_group(nodes.first);
	int groupY = someSet.find_group(nodes.second);
	if(groupX == groupY)
	     continue;
	someSet.unite(nodes.first,nodes.second);
	mst_indexes.push_back(i);
	mst_cost+=*v[i].get_cost();
          }
     }
     void print_mst(){
          printf("%d\n",mst_cost);
          printf("%d\n",mst_indexes.size());
          for(int i = 0 ; i < mst_indexes.size(); i++){
	pair<int,int> nodes = v[mst_indexes[i]].getNodes();
	printf("%d %d\n",nodes.second,nodes.first);
          }
     }
};

int main(){
     
     freopen("apm.in","r",stdin);
     freopen("apm.out","w",stdin);
     int n,m;
     scanf("%d %d",&n,&m);
     Graph myGraph(n,m);
     for(int i = 0 ; i< m; i++){
          int x,y,c;
          scanf("%d%d%d",&x,&y,&c);
          Edge someEdge(x,y,c);
          myGraph.insert_edge(someEdge);
     }
     myGraph.sort_edges_after_cost();
    // myGraph.print_edges();
     myGraph.compute_mst();
     myGraph.print_mst();
     return 0;
}