#include <fstream>
#include <algorithm>
#define nMax 200005
#define mMax 400005
#define piii pair<int, pair<int, int> >
#define x first
#define y second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, Sol, nrUsed, Root[nMax];
piii Edge[mMax], Used[mMax];
void read()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>Edge[i].y.x>>Edge[i].y.y>>Edge[i].x;
}
int getRoot(int node)
{
    return (Root[node]<0) ? node : Root[node]=getRoot(Root[node]);
}
int cmp(piii a, piii b)
{
    return a.x<b.x;
}
void apm()
{
    for(int i=1;i<=n;i++)
        Root[i]=-1;
    sort(Edge+1, Edge+m+1, cmp);
    for(int i=1;i<=m;i++)
    {
        int val1=getRoot(Edge[i].y.x);
        int val2=getRoot(Edge[i].y.y);
        if(val1!=val2)
        {
            switch(Root[val1]-Root[val2]<=0)
            {
                case 1:Root[val1]+=Root[val2];Root[val2]=val1;break;
                case 0:Root[val2]+=Root[val1];Root[val1]=val2;break;
            }
            Sol+=Edge[i].x;
            Used[++nrUsed]=Edge[i];
        }
    }
}
void write()
{
    fout<<Sol<<'\n'<<nrUsed<<'\n';
    for(int i=1;i<=nrUsed;i++)
        fout<<Used[i].y.x<<" "<<Used[i].y.y<<'\n';
}
int main()
{
    read();
    apm();
    write();
    return 0;
}