#include <iostream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
int roots[200005];
struct drum{
int firstNode;
int secondNode;
int cost;
};
void initRoots(int n){
    for(int i=1;i<=n;i++)
        roots[i]=i;
}
vector<drum> theVertices;
vector<drum> theResultArray;
int sum=0;
bool comp(drum a,drum b){
    if(a.cost>b.cost)
        return false;
    else if(a.cost==b.cost)
        if(a.firstNode>b.firstNode)
        return false;
        else
            return true;
    return true;
}
int getRoot(int a){
if(a!=roots[a])
    return getRoot(roots[a]);
else
    return a;

}
void setUnion(int a,int b){
    roots[getRoot(b)]=getRoot(a);
}

void kruskal(){
    int sizeOfArray=theVertices.size();
    for(int i=0;i<sizeOfArray;i++)
    {

        int r1=getRoot(theVertices[i].firstNode);
        int r2=getRoot(theVertices[i].secondNode);
        if(r1!=r2)
        {
            sum+=theVertices[i].cost;
            theResultArray.push_back(theVertices[i]);
            setUnion(theVertices[i].firstNode,theVertices[i].secondNode);
        }
    }

}
int main()
{
    fin>>n>>m;
    initRoots(n);
    for(int i=0;i<m;i++){
        int x,y,cost;
        fin>>x>>y>>cost;
        theVertices.push_back({x,y,cost});
    }
    sort(theVertices.begin(),theVertices.end(),comp);
    kruskal();
    fout<<sum<<"\n";
    fout<<theResultArray.size()<<"\n";
    for(int i=0;i<theResultArray.size();i++)
        fout<<theResultArray[i].secondNode<<" "<<theResultArray[i].firstNode<<"\n";
    return 0;
}