#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x,y,z,sol[200001],tata[200001];
struct numar
{
    int x,y,cost;
};
vector <numar> M;
int cmp(numar a,numar b)
{
    return a.cost<b.cost;
}
int rad(int x)
{
    while(tata[x]>0)
        x=tata[x];
    return x;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        tata[i]=-1;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        M.push_back({x,y,z});
    }
    sort(M.begin(),M.end(),cmp);
    int k=0;
    int cost=0;
    for(int i=0;k<n-1;i++)
    {
        x=M[i].x;
        y=M[i].y;
        z=M[i].cost;

        if(rad(x)!=rad(y))
        {
            k++;
            x=rad(x);
            y=rad(y);
            if(tata[x]>tata[y])
                swap(x,y);
            tata[x]+=tata[y];
            tata[y]=x;
            cost+=z;
            sol[k]=i;

        }


    }
    fout<<cost<<"\n";
    fout<<k<<"\n";
    for(int i=1;i<=k;i++)
    {
        fout<<M[sol[i]].x<<" "<<M[sol[i]].y<<"\n";
    }


    return 0;
}