#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int Nmax=400000;
struct muchie
{
    int x,y,c;
};
muchie v[Nmax+5];
muchie sol[(Nmax>>1)+5];
int t[(Nmax>>1)+5];
int Find(int x)
{
    int r=x;
    while(t[r]!=r)
        r=t[r];
    ///+path compression
    while(t[x]!=r)
    {
        int w=t[x];
        t[x]=r;
        x=w;
    }
    return r;
}
void Union(int x,int y)
{
    int p=Find(x);
    int q=Find(y);
    if(p!=q)
        t[p]=q;
}
void Interclasare(int p,int u,int m)
{
    int i,j,k=0;
    muchie a[u-p+1]= {0};
    i=p;
    j=m+1;
    while(i<=m && j<=u)
    {
        if(v[i].c>v[j].c)
            a[++k]=v[j],j++;
        else
            a[++k]=v[i],i++;
    }
    if(i<=m)
        while(i<=m)
            a[++k]=v[i],i++;
    if(j<=u)
        while(j<=u)
            a[++k]=v[j],j++;
    for(int i=1; i<=k; i++)
        v[p+i-1]=a[i];
}
void Divide(int p,int u)
{
    int m;
    if(u<=p+1)
    {
        ///daca avem cel putin 2 elemente in bucatica creata
        if(v[p].c>v[u].c)
            swap(v[p],v[u]);
    }
    else
    {
        m=(p+u)/2;
        Divide(p,m);
        Divide(m+1,u);
        Interclasare(p,u,m);
    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    int nr=0;
    while(m--)
    {
        nr++;
        fin>>v[nr].x>>v[nr].y>>v[nr].c;
    }
    Divide(1,nr);
    for(int i=1; i<=n; i++)
        t[i]=i;
    int nrsel=0;
    int k=1,cost=0;
    do
    {
        // if(nrsel==n-1)break;
        int p1=Find(v[k].x);
        int p2=Find(v[k].y);
        if(p1!=p2)
        {
            nrsel++;
            cost+=v[k].c;
            sol[nrsel].x=v[k].x;
            sol[nrsel].y=v[k].y;
            Union(v[k].x,v[k].y);
        }
        k++;
    }
    while(nrsel!=n-1);
    fout<<cost<<"\n"<<nrsel<<"\n";
    for(int i=1; i<=nrsel; i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
}