#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200099
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int N, M, cost, T[NMAX], sol[NMAX];
struct edge
{
  int x,y,c;
}aux;
vector <edge> E;

bool cmp (edge A, edge B)
{
    if (A.c<B.c)return 1;
    return 0;
}


int gr(int x)
{
    if(T[x]!=x) T[x]=gr(T[x]);
    return T[x];
}

void Reuneste(int x, int y)
{
    T[gr(x)] = gr(y);
}

void Kruskal()
{
    sort(E.begin(), E.end(), cmp);
    for (int i=1; i<=N; i++)T[i]=i;
    for (int i=0; i<=M-1 && sol[0]!=N-1; i++)
        if(gr(E[i].x)!=gr(E[i].y))
            cost+=E[i].c, sol[++sol[0]]=i, Reuneste(E[i].x, E[i].y);
}

int main()
{
    f>>N>>M;
    for(int i=1; i<=M;i++)
        f>>aux.x>>aux.y>>aux.c, E.push_back(aux);
    Kruskal();
    g<<cost<<'\n';
    g<<sol[0]<<'\n';
    for(int i=1; i<=sol[0];i++)
        g<<E[i].x<<' '<<E[i].y<<'\n';
    f.close(); g.close();
    return 0;
}