/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x[400002],y[400002],c[400002],t[200002],ind[400002],cnt,vans[200002],sol;
int tata(int x)
{
    if(t[x]==x) return x;
    t[x]=tata(t[x]);
    return t[x];
}
void reuniune(int a,int b)
{
    t[tata(a)]=tata(b);
}
bool cmpf(int a, int b)
{
    return(c[a]<c[b]);
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x[i]>>y[i]>>c[i];
        ind[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        sort(ind+1,ind+1+m,cmpf);
    }
    for(int i=1;i<=m;i++)
    {
        if(tata(x[ind[i]])!=tata(y[ind[i]]))
        {
            sol=sol+c[ind[i]];
            reuniune(x[ind[i]],y[ind[i]]);
            cnt++;
            vans[cnt]=ind[i];
        }
    }
    fout<<sol<<'\n'<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
    {
        fout<<x[vans[i]]<<" "<<y[vans[i]]<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}