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

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

vector<int> p(1), ans;

int gp(int v);
void mr(int r, int t);
bool mf(mc x, mc y){ return(x.c<y.c); }
       
int main(){
    int n,m,s=0;
    ifstream cinr ("apm.in");
    ofstream cour ("apm.out");
    cinr >> n; cinr >> m;
    mc g[m];
    for(int i=1; i<=n; i++) p.push_back(i);
    
    for(int i=0; i<m; i++){
            cinr >> g[i].a;
            cinr >> g[i].b;
            cinr >> g[i].c;
            }
    cinr.close();
    
    sort(g, g+m, mf);        
    for(int i=0; i<m; i++){
            if( gp(g[i].a)!=gp(g[i].b) ){
                s+=g[i].c;
                ans.push_back(i);
                mr(g[i].a, g[i].b);
                }
            }
            
    cour << s << "\n" << n-1 << "\n";
    for(int i=0; i<n-1; i++) cour << g[ans[i]].a << " " << g[ans[i]].b << "\n";
    cour.close();
    return 0;
    }

int gp(int v){
    if(v==p[v]) return(v);
    return( p[v]=gp(p[v]) );
    }
    
void mr(int r, int t){
     r=gp(r);
     t=gp(t);
     p[r]=t;
     }