#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#define nmax 200005
using namespace std;
struct muchie{int x,y,cost;};
vector <struct muchie> Muchii;
vector <struct muchie> alese;
int rang[nmax],tata[nmax];
bool comp(struct muchie A, struct muchie B)
{
    return A.cost<B.cost;
}
int reprezentant(int x)
{
    if (x==tata[x])
        return x;
    tata[x]=reprezentant(tata[x]);
    return tata[x];
    //compresia drumurilor
}
int reuneste(int x, int y)
{
    if (rang[x]<rang[y])
    {
        tata[x]=y;
        rang[y]+=(rang[x]+1);
    }
    else
    {
        tata[y]=x;
        rang[x]+=(rang[y]+1);
    }
}
int solve(int n)
{
    muchie e;
    int i,nrmuchii=0,x,y,total=0;
    for (i=0;i<Muchii.size() && nrmuchii<n-1;i++)
    {
        e=Muchii[i];
        x=reprezentant(e.x);
        y=reprezentant(e.y);
        if (x!=y)
        {
            reuneste(x,y);
            nrmuchii++;
            alese.push_back(e);
            total+=e.cost;
        }
    }
    return total;
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m,i;
    muchie e;
    fin>>n>>m;
    for (;m;m--)
    {
        fin>>e.x>>e.y>>e.cost;
        Muchii.push_back(e);
    }
    for (i=1;i<=n;i++)
        tata[i]=i;
    sort(Muchii.begin(),Muchii.end(),comp);
    fout<<solve(n)<<'\n';
    fout<<alese.size()<<'\n';
    for (i=0;i<alese.size();i++)
    {
        e=alese[i];
        fout<<e.x<<' '<<e.y<<'\n';
    }
    Muchii.clear();
    alese.clear();
    fin.close();
    fout.close();
    return 0;
}