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

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

struct edge{
    int x,y,cost;
    bool operator < (const edge & other){
        return cost < other.cost;
    }
}muchii[400005];

int rang[400005],parinte[400005],N,M,X,Y,C;
stack<pair<int,int>> rez;

int FindRoot(int x){
    if(parinte[x]==x) return x;
    else return parinte[x]=FindRoot(parinte[x]);
}

void Union(int x,int y){
    x=FindRoot(x);
    y=FindRoot(y);
    if(x==y) return;
    if(rang[x]<rang[y]) swap(x,y);
    if(rang[x]==rang[y]) rang[x]++;
    parinte[y]=x;
}


void citire(){
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        fin>>X>>Y>>C;
        muchii[i].x=X;
        muchii[i].y=Y;
        muchii[i].cost=C;
    }
    for(int i=1;i<=N;i++){
        parinte[i]=i;
        rang[i]=1;
    }
    sort(muchii+1, muchii+M+1);
}

int main()
{
    citire();
    int cnt=0,sum=0;
    for(int i=1;i<=M;i++){
        int nod1=muchii[i].x;
        int nod2=muchii[i].y;
        if(FindRoot(nod1)!=FindRoot(nod2)){
            Union(nod1,nod2);
            sum+=muchii[i].cost;
            cnt++;
            rez.push({nod1, nod2});
        }
    }
    fout<<sum<<"\n"<<cnt<<"\n";
    while(!rez.empty()){
        fout<<rez.top().first<<" "<<rez.top().second<<"\n";
        rez.pop();
    }
    return 0;
}