#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");



vector <int> l[200001];
pair <int , int> v[400001];
int cost[400001],viz[200001];

void viz0(){
    for(int i=1;i<=200001;i++)
            viz[i]=0;
}
    

void sortare(int m){
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
            if(cost[j]<cost[i])
                swap(cost[i],cost[j]),swap(v[i],v[j]);
}

void dfs(int node){
    for(int i: l[node])
        if(viz[i]==0){
            viz[i]=1;
            dfs(i);
        }
}

void afisare(int s, int k,int n){
    int vizi[101]={0};
    fout<<s<<endl<<k<<endl;
    for(int i=1;i<=n;i++){
        for(int j:l[i])
            if(vizi[i]+vizi[j]<2){
                fout<<i<<" "<<j<<endl;
                vizi[i]=1;
                vizi[j]=1;
            }
                
    }
}

int main() {
    int n,m;
    int x,y,z;
    int s=0,k=1;
    
    
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        
        fin>>x>>y>>z;
        v[i]={x,y};
        cost[i]=z;
    }
    sortare(m);
    l[v[1].first].push_back(v[1].second);
    l[v[1].second].push_back(v[1].first);
    int pr=l[v[1].second].front();
    dfs(pr);
    s+=cost[1];
    
    

    for(int i=2;i<=m;i++){
        if(viz[v[i].first]+viz[v[i].second]<2){
            viz0();
            l[v[i].first].push_back(v[i].second);
            l[v[i].second].push_back(v[i].first);
            s+=cost[i];
            k++;
            dfs(pr);
        }
    }
    
    
    
    afisare(s,k,n);
    
    return 0;
}