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

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

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

bool adv(edge a,edge b){
    return a.cost<b.cost;
}

vector<edge> graf;
vector<pair<int,int> > parinte,sol;

int getroot(int a){
    if(parinte[a].first==-1)return a;
    return parinte[a].first=getroot(parinte[a].first);
}

void makeuni(int a,int b){
    a=getroot(a),b=getroot(b);
    if(a!=b){
        if(parinte[a].second<parinte[b].second)swap(a,b);
        parinte[b].first=a;
        if(parinte[a].second==parinte[b].second)parinte[a].second++;
    }

}






int n,m,x,y,c,s,nr;




int main()
{
    fin>>n>>m;
    graf.resize(m);
    parinte.assign(n,{-1,1});
    for(int i=0;i<m;i++){
        fin>>graf[i].x>>graf[i].y>>graf[i].cost;
        graf[i].x--;
        graf[i].y--;
    }

    sort(graf.begin(),graf.end(),adv);

    for(int i=0;i<m;i++){
        x=graf[i].x;
        y=graf[i].y;
        c=graf[i].cost;
        if(getroot(x)!=getroot(y)){
            makeuni(x,y);
            s+=c;
            nr+=1;
            sol.push_back({x,y});
        }
    }
    fout<<s<<'\n'<<nr<<'\n';
    for(int i=0;i<nr;i++){
        fout<<sol[i].first+1<<" "<<sol[i].second+1<<'\n';
    }

}