#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 200005;
int dim[NMAX],parent[NMAX];
int n,m,dim_rasp,cost_final;
pair<int,int> rasp[NMAX];

struct apm{
    int x,y,cost;
};

apm a[NMAX];

bool cmp(apm nr1,apm nr2){
    return nr1.cost<nr2.cost;
}

void citire(){
    fin >> n >> m;
    for(int i=1;i<=m;i++){
        fin >> a[i].x >> a[i].y >> a[i].cost;
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=n;i++){
        parent[i]=i;
        dim[i]=1;
    }
}

int get_root(int node){
    while(parent[node]!=node){
        node=parent[node];
    }
    return node;
}

bool unesc(int node1,int node2){
    int root1=get_root(node1);
    int root2=get_root(node2);
    if(root1==root2) return false;
    if(dim[root1]<=dim[root2]){
        parent[root1]=root2;
        dim[root2]+=dim[root1];
    } else {
        parent[root2]=root1;
        dim[root1]+=dim[root2];
    }
    return true;
}

void solve(){
    for(int i=1;i<=m;i++){
        int node1 = a[i].x;
        int node2 = a[i].y;
        int r1=get_root(node1),r2=get_root(node2);
        if(unesc(node1,node2)==true){
            rasp[++dim_rasp]={r1,r2};
            cost_final+=a[i].cost;
        }
    }
}

void afis(){
    fout << cost_final << '\n';
    fout << dim_rasp << '\n';
    for(int i=1;i<=dim_rasp;i++){
        fout << rasp[i].first << ' ' << rasp[i].second << '\n';
    }
}

int main()
{
    citire();
    solve();
    afis();
    return 0;
}