#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

struct cell{
       int a,b,c;
       };

int getParent(int a, int parent[]){
    if(parent[a]==a) return a;
    return parent[a]=getParent(parent[a], parent);
    }

bool comp(cell x, cell y){
     return x.c<y.c;
     }

int main(){
    int n,m;
    ifstream cinr("apm.in");
    cinr >> n >> m;
    cell edges[m]; int p[m];
    for(int i=0; i<m; i++){
            p[i]=i;
            cinr >> edges[i].a >> edges[i].b >> edges[i].c;
            }
    cinr.close();
    sort(edges, edges+m, comp);
    
    cell res[n-1];
    int sum=0, k=0; 
    for(int i=0; i<m; i++){
            if(getParent(edges[i].a, p)!=getParent(edges[i].b, p)){
                                     p[p[edges[i].a]]=p[edges[i].b];
                                     sum+=edges[i].c;
                                     res[k]=edges[i]; k++;
                                     }
            }
            
    ofstream cour("apm.out");
    cour << sum << "\n" << n-1 << "\n";
    for(int i=0; i<n-1; i++)
            cour << res[i].a << " " << res[i].b << "\n";
    cour.close();
    }