#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int mmax=400005,nmax=200005;
int n,m,viz[nmax];
struct graph
{
    int x,y,c;
}a[mmax];
struct solution
{
    int from,to;
}ans[mmax];
bool cmp(graph a, graph b)
{
    return a.c<b.c;
}
void read_data()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
}
void apm()
{
    int nrm=0,s=0,k=0,i,j,mark;
    bool ok=0;
    for(i=1;i<=n;i++)
        viz[i]=i;
    i=1;
    while(i<=m)
    {
        if(viz[a[i].x]!=viz[a[i].y])
        {
            nrm++;
            s+=a[i].c;
            //ok=1;
            int comp1=viz[a[i].x];
            int comp2=viz[a[i].y];
            for(j=1;j<=n;j++)
                if(viz[j]==comp2)
                    viz[j]=comp1;
            k++;
            ans[k].from=a[i].x;
            ans[k].to=a[i].y;
        }
        i++;
    }
    fout<<s<<'\n';
    fout<<nrm<<'\n';
    for(i=1;i<=k;i++)
        fout<<ans[i].from<<' '<<ans[i].to<<'\n';
}
int main()
{
    read_data();
    sort(a+1,a+m+1,cmp);
    apm();
}