#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define mmax 400006
using namespace std;
vector<int> T,Rang;
int n,m,costmin,k,p;
struct muchii
{
    int x,y,cost;
} v[mmax];

struct marb
{
    int x,y;
} varb[mmax];
//vector<int> l[mmax/2];

bool compare(muchii a, muchii b)
{
    if(a.cost>b.cost)
        return false;
    return true;
}
int cauta(int x)
{
    int R=x,aux;
    while(R!=T[R])
        R=T[R];

    while(T[x]!=x)
     {
         aux=T[x];
         T[x]=R;
         x=aux;
     }
    return R;
}

void join(int x, int y)
{
    if(Rang[x]>Rang[y])
        T[y]=x;
    else T[x]=y;
    if(Rang[x]==Rang[y])
        Rang[y]++;
}


void Read()
{
    ifstream f("apm.in");
    f>>n>>m;
    T.resize(n+1);
    Rang.resize(n+1);
    for(int i=1; i<=n; i++)
    {
        T[i]=i;
        Rang[i]=0;
    }
    int x,y,cost;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>cost;
        v[i].x=x;
        v[i].y=y;
        v[i].cost=cost;
        //l[x].push_back(y);
        //l[y].push_back(x);
    }
}

void apm()
{
    int xa,ya;
    for(int i=1; k<n-1; i++)
    {
        xa=cauta(v[i].x);
        ya=cauta(v[i].y);
        if(xa!=ya)
        {
            varb[++k].x=v[i].x;
            varb[k].y=v[i].y;
            costmin+=v[i].cost;
            join(xa,ya);
        }
    }
}

void Write()
{
    ofstream g("apm.out");
    g<<costmin<<'\n'<<k<<'\n';
    for(int i=1; i<=k; i++)
        g<<varb[i].x<<" "<<varb[i].y<<'\n';
}

int main()
{
    Read();
    sort(v+1,v+m+1,compare);
    apm();
    Write();
    return 0;
}