#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;
}
struct rad
{
    int root;
    int rang;
};
rad getRoot(rad a)
{

    if(a.root!=roots[a.root])

    {
        ++a.rang;
        return getRoot({roots[a.root],a.rang+1});

    }
    else
        return a;

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

void kruskal()
{
    int sizeOfArray=theVertices.size();
    for(int i=0; i<sizeOfArray; i++)
    {
        if(theResultArray.size()<n)
        {
            rad r1=getRoot({theVertices[i].firstNode,0});
            rad r2=getRoot({theVertices[i].secondNode,0});
            if(r1.root!=r2.root)
            {
                sum+=theVertices[i].cost;
                if(r1.rang>r2.rang){
                     setUnion(theVertices[i].firstNode,theVertices[i].secondNode);
                }
                else{
                    setUnion(theVertices[i].secondNode,theVertices[i].firstNode);
                }

                theResultArray.push_back(theVertices[i]);

            }
        }
    }

}
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";
    int sizeCool=theResultArray.size();
    fout<<sizeCool<<"\n";
    for(int i=0; i<sizeCool; i++)
        fout<<theResultArray[i].secondNode<<" "<<theResultArray[i].firstNode<<"\n";
    return 0;
}