#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define mmax 400002
using namespace std;
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;
}


void Read()
{
    ifstream f("apm.in");
    f>>n>>m;
    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 c[mmax/2];
    for(int i=1;i<=n;i++)
        c[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(c[v[i].x]!=c[v[i].y])
        {
            varb[++k].x=v[i].x;
            varb[k].y=v[i].y;
            costmin+=v[i].cost;
            int aux=c[v[i].x];
            c[v[i].x]=c[v[i].y];
            for(int j=1;j<=n;j++)
            {
                if(c[j]==aux)
                    c[j]=c[v[i].y];
            }
        }
    }
}

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;
}