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

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

const int dim=200009,inf=1e8;

struct muchie{
    int x,y,c;
    bool operator <(muchie const &a)const
    {
        return c<a.c;
    }
};

vector<muchie>v;
vector<pair<int,int>>ans;

int Parent[dim];
int Rank[dim];

int find_set(int x){
    if(Parent[x]==x)
        return x;
    return Parent[x]=find_set(Parent[x]);
}

void union_set(int x,int y){
    int a=find_set(x);
    int b=find_set(y);
    if(a!=b){
        if(Rank[a]<Rank[b]){
            swap(a,b);
        }
        Parent[b]=a;
        if(Rank[a]==Rank[b])
            Rank[a]++;
    }
}

signed main(){
    int n,m,cost=0;
        fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        v.push_back({x,y,c});
    }
    sort(v.begin(),v.end());

    for(int i=1;i<=n;i++){
        Parent[i]=i;
        Rank[i]=0;
    }

    for(auto e:v){
        if(find_set(e.x)!=find_set(e.y)){
            cost+=e.c;
            union_set(e.x,e.y);
            ans.push_back({e.x,e.y});
        }
    }
        fout<<cost<<'\n';
        fout<<ans.size()<<'\n';
    for(auto it:ans){
        fout<<it.first<<' '<<it.second<<'\n';
    }
}