#include <stdlib.h>
#include <set>
#include <vector>
#include <fstream>
#include <iostream>

using namespace std;

struct muchie{
    int a,b,cost;
    bool operator<(const muchie& l)const{
        if(l.a==a){return l.b<b;}
        return l.a<a;
    }

    bool operator==(const muchie& l)const{
        return (l.a==a && l.b==b);
    }
};

int comp(const void *a, const void *b){
    return ((muchie *)a)->cost-((muchie *)b)->cost;
}

set<muchie>graf;
vector<muchie>muchii;
vector<int>parinte;

int FindSet(int u){
    if(parinte[u]==0)return u;
    return parinte[u] = FindSet(parinte[u]);
}

int Union(int u,int v){
    parinte[u] = v;
}

void kruskal(int noduri,int much){
    qsort(&muchii[0],much,sizeof(muchie),comp);
    for(int i=0;i<=noduri;i++){
            parinte.push_back(0);
    }
    int muchiifin=0,itmuch=0;
    muchie act;
    while(muchiifin<noduri-1){
        act = muchii[itmuch];
        int parintea = FindSet(act.a);
        int parinteb = FindSet(act.b);
        if(parintea!=parinteb){
            muchie temp;
            temp.a=act.a;
            temp.b=act.b;
            temp.cost=act.cost;
            graf.insert(temp);
            Union(parintea,parinteb);
            muchiifin++;
        }
        itmuch++;
    }
}

int main(){
    fstream f("apm.in",ios::in);
    int nod,much;
    f>>nod>>much;
    int i,j;
    int ma,mb,mc;
    for(i=0;i<much;i++){
        f>>ma>>mb>>mc;
        muchie temp;
        temp.a = ma;
        temp.b = mb;
        temp.cost = mc;
        muchii.push_back(temp);
    }f.close();
    kruskal(nod,much);
    fstream g("apm.out",ios::out);
    int costt=0;
    for(set<muchie>::iterator it=graf.begin();it!=graf.end();it++){
        costt+=it->cost;
    }
    g<<costt<<"\n"<<graf.size()<<"\n";
    for(set<muchie>::iterator it=graf.begin();it!=graf.end();it++){
        //cout<<it->a<<" "<<it->b<<" "<<it->cost<<endl;
        g<<it->a<<" "<<it->b<<"\n";
    }
    return 0;
}