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

struct muchie{
    int v1,v2,cost;
};

ifstream fin("apm.in");
ofstream fout("apm.out");
vector <pair<int,int>> muchii_apcm;
muchie muchii[400001];
int tata[200001],height[200001],cost_total,n,m;

void Init(int x){
    tata[x]=height[x]=0;
}

int Reprezentant(int x){
    if(tata[x]==0) return x;
    tata[x]=Reprezentant(tata[x]);
    return tata[x];
}

void Reunire(int x,int y){
    int rx,ry;
    rx=Reprezentant(x);
    ry=Reprezentant(y);
    if(height[rx]>height[ry]) tata[ry]=rx;
    else{
        tata[rx]=ry;
        if(height[rx]==height[ry]) height[ry]++;
    }
}

int comparatie(muchie x,muchie y){
    if(x.cost<y.cost)return 1;
    return 0;
}

void Kruskal(){
    int nrmsel=0,muchia=0,u,v,i;
    for(v=1;v<=n;++v)Init(v);
    sort(muchii,muchii+m,comparatie);
    for(;muchia<m;++muchia){
        u=muchii[muchia].v1;
        v=muchii[muchia].v2;
        if(Reprezentant(u)!=Reprezentant(v)){
            nrmsel++;
            muchii_apcm.push_back({u,v});
            cost_total+=muchii[muchia].cost;
            Reunire(u,v);
        }
        if(nrmsel==n-1)break;
    }
}

int main(){
    fin>> n;
    fin>> m;
    
    for(int i=0;i<m;++i){
        fin>>muchii[i].v1>>muchii[i].v2>>muchii[i].cost;
    }
    Kruskal();
    fout<<cost_total<<"\n"<<n-1<<"\n";
    for(int i=0;i<muchii_apcm.size();++i)
        fout<<muchii_apcm[i].first<<" "<<muchii_apcm[i].second<<"\n";    
}