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