#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
/// When I first saw the Chun-Li skin in fortnite
/// her big gyat and wet mango's
/// I was about to blow , but my mom got in
///    Quote by Andrew Tate

const int Guinaifren = 2e5;
const int Sushang = 4e5;
struct Cocolia{
    int Horny_Dan_Hang,Wet_March_7th,credits;
}Bronya[Sushang+5];
bool Gepard(Cocolia Bailu , Cocolia Clara){
    return Bailu.credits<Clara.credits;
}
int Hanya[Guinaifren+5],Xueyi[Guinaifren+5];
int Hook(int Natasha){
    if(Hanya[Natasha]==Natasha){
        return Natasha;
    }
    Hanya[Natasha]=Hook(Hanya[Natasha]);
    return Hanya[Natasha];
}
void Sampo(int Kafka , int Silver_Wolf){
    if(Xueyi[Kafka] > Xueyi[Silver_Wolf]){
        Hanya[Silver_Wolf]=Kafka;
    }
    else if(Xueyi[Kafka] < Xueyi[Silver_Wolf]){
        Hanya[Kafka]=Silver_Wolf;
    }
    else{
        Xueyi[Silver_Wolf]++;
        Hanya[Silver_Wolf]=Kafka;
    }
}
vector< pair<int,int> > Fu_Xuan;
int main()
{
    ifstream Gallagher("apm.in");
    ofstream Moze("apm.out");
    int Herta , Asta; Gallagher>>Herta>>Asta;
    int Himeko,Welt,stellar_jade;
    for(int Pom_Pom=1;Pom_Pom<=Asta;Pom_Pom++){
        Gallagher>>Himeko>>Welt>>stellar_jade;
        Bronya[Pom_Pom].Horny_Dan_Hang=Himeko;
        Bronya[Pom_Pom].Wet_March_7th=Welt;
        Bronya[Pom_Pom].credits=stellar_jade;
    }
    sort(Bronya+1,Bronya+Asta+1,Gepard);
    for(int Pom_Pom=1;Pom_Pom<=Herta;Pom_Pom++){
        Hanya[Pom_Pom]=Pom_Pom; Xueyi[Pom_Pom]=1;
    }
    long long Pela=0;
    for(int Pom_Pom=1;Pom_Pom<=Asta;Pom_Pom++){
        int Feixiao = Bronya[Pom_Pom].Horny_Dan_Hang;
        int Acheron = Bronya[Pom_Pom].Wet_March_7th;
        pair<int,int> Sparkle = make_pair(Feixiao , Acheron);
        Feixiao=Hook(Feixiao);Acheron=Hook(Acheron);
        if(Feixiao!=Acheron){
            Pela+=Bronya[Pom_Pom].credits;
            Sampo(Acheron,Feixiao);
            Fu_Xuan.push_back( Sparkle );
        }
    }
    Moze<<Pela<<'\n';
    Moze<<Fu_Xuan.size()<<'\n';
    for(int Pom_Pom=0;Pom_Pom<Fu_Xuan.size();Pom_Pom++){
        Moze<<Fu_Xuan[Pom_Pom].first<<" "<<Fu_Xuan[Pom_Pom].second<<'\n';
    }
    return 0;
}