#include <bits/stdc++.h>
using namespace std;

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

int n, M, nod1, nod2, cost;
struct muchie{
    int n1, n2, c;
};
muchie v[400005];
int m[200005], sz[200005];
vector<pair<int, int>>sol;


bool comp( muchie A, muchie B){
    return A.c<B.c;
}

int Find(int x){
    int root=x;

    while(m[root]!=root){
        root=m[root];
    }
    while(m[x]!=x){
        int copie=m[x];
        m[x]=root;
        x=copie;
    }
    return root;
}

void Union(int x, int y){
    int rootX=Find(x);
    int rootY=Find(y);

    if(sz[rootX]>sz[rootY]){
        sz[rootX]+=sz[rootY];
        m[rootY]=m[rootX];
    }
    else{
        sz[rootY]+=sz[rootX];
        m[rootX]=m[rootY];
    }
}

int main(){
    fin>>n>>M;
    for(int i=1;i<=M;i++){
        fin>>nod1>>nod2>>cost;
        v[i].n1=nod1;
        v[i].n2=nod2;
        v[i].c=cost;
    }
    sort(v+1, v+M+1, comp);
    for(int i=1;i<=n;++i){
        m[i]=i;
        sz[i]=1;
    }
    cost=0;
    for(int i=1;i<=M && sol.size()<=n-1;i++){
        if(Find(v[i].n1)!=Find(v[i].n2)){
            Union(v[i].n1, v[i].n2);
            cost+=v[i].c;
            sol.push_back({v[i].n1, v[i].n2});
        }
    }
    fout<<cost<<"\n";
    fout<<sol.size()<<"\n";
    for(int i=0;i<sol.size();++i)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";


    return 0;
}