#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;


class DSU{
    int p[dim],sz[dim];
public:
    DSU(int n){
        for(int i=1;i<=n;i++){
            p[i]=i;
            sz[i]=1;
        }
    }
    int find_set(int x){
        if(p[x]==x)
            return x;
        return p[x]=find_set(p[x]);
    }
    void union_set(int x,int y){
        int a=find_set(x);
        int b=find_set(y);
        if(a!=b){
            if(sz[a]<sz[b]){
                swap(a,b);
            }
            p[b]=a;
            sz[a]+=sz[b];
        }
    }
};

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());
    DSU apm(n);
    for(auto e:v){
        if(apm.find_set(e.x)!=apm.find_set(e.y)){
            cost+=e.c;
            apm.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';
    }
}