#include<bits/stdc++.h>

using namespace std;

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

struct str{
    int x,y,c;
};

bool comp(str a,str b){
    if(a.c>=b.c) return false;
    return true;
}

vector<int>t;
vector<pair<int,int>>apm;
vector<str> v;
int n,m;

int root(int x){
    if(x==t[x]) return x;
    else return(t[x]=root(t[x]));
}

int main(){
    t.resize(200067);
    fin>>n>>m;
    while(m--){
        int x,y,c;
        fin>>x>>y>>c;
        v.push_back({x,y,c});
    }
    for(int i=1;i<=200067;i++)t[i]=i;
    int rez=0;
    sort(v.begin(),v.end(),comp);
    for(auto f:v){
        int ra=root(f.x),rb=root(f.y);
        if(ra!=rb){
            t[ra]=rb;
            apm.push_back({f.x,f.y});
            rez+=f.c;
        }
    }
    fout<<rez<<'\n'<<n-1<<'\n';
    for(auto x:apm) fout<<x.first<<" "<<x.second<<'\n';
    return 0;
}