#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int Nmax = 400001;
int n, m, total, ct=0;
int grad[Nmax];

struct clasa{int x,y,cost;};
struct coord{int x,y;};

coord rez[Nmax];

vector <clasa> lista;
vector <int> a[Nmax];

bool srtt(clasa i, clasa j)
{
    return i.cost<j.cost;
}

void citire()
{
    in >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int cost, x, y;
        in >> x >> y >> cost;
        lista.push_back(clasa{x,y,cost});
    }
}

void uniune(int grad_min, int grad_max)
{
    for(int i=0; i<a[grad_max].size(); i++)
    {
        a[grad_min].push_back(a[grad_max][i]);
        grad[a[grad_max][i]]=grad_min;
    }
    a[grad_max].clear();
}

void kruskal()
{
    sort(lista.begin(), lista.end(), srtt);
    for(int i=1; i<=n; i++) {grad[i]=i;a[i].push_back(i);}
    for(int i=0; i<m; i++)
    {
        if(grad[lista[i].x] != grad[lista[i].y])
        {
            ct++; rez[ct].x=lista[i].x;
                  rez[ct].y=lista[i].y;
            total+=lista[i].cost;
            int grad_min=min(grad[lista[i].x],grad[lista[i].y]);
            int grad_max=max(grad[lista[i].x],grad[lista[i].y]);
            uniune(grad_min, grad_max);
        }
    }
}

void afisare()
{
    out<<total<<'\n'<<m-1<<'\n';
    for(int i=1; i<n; i++)
        out<<rez[i].x<<' '<<rez[i].y<<'\n';
}

int main ()
{
    citire();
    kruskal();
    afisare();
    return 0;
}