#include <fstream>
#include <algorithm>

#define NMAX 200002
#define MMAX 400002
using namespace std;

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

struct muchie{int x, y, cost;};

int n, m;

muchie M[NMAX];

int root[NMAX];

void citire();
void APM();
void uneste(int x, int y);
int gaseste(int x);

bool compcost(muchie a, muchie b)
{
 return a.cost < b.cost;
}
int main()
{
    citire();
    APM();
    return 0;
}

void citire()
{
 int i;
 fin>>n>>m;
 for(i = 1; i <= m; i++)
    fin>>M[i].x>>M[i].y>>M[i].cost;
}

void APM()
{
 int i, costmin = 0, nr = 0; //nr = nr de muchii din solutii, costmin = costul solutiei
 int solutie[MMAX]; //va contine nr de ordine ale muchiilor pe care le selectez
 for(i = 1; i <= n; i++) root[i] = i;
 sort(M + 1, M + m + 1, compcost);
 for(i = 1; i <= m; i++)
 {
    root[M[i].x] = gaseste(M[i].x);
    root[M[i].y] = gaseste(M[i].y);
    if(root[M[i].x] != root[M[i].y])
    {
       uneste(root[M[i].x], root[M[i].y]);
       solutie[++nr] = i;
       costmin += M[i].cost;
    }
 }
 fout<<costmin<<'\n';
 fout<<nr<<'\n';
 for(i = 1; i <= nr; i++)
    fout<<M[solutie[i]].x<<' '<<M[solutie[i]].y<<'\n';
}

void uneste(int x, int y)
{
 root[x] = gaseste(x);
 root[y] = gaseste(y);
 root[root[y]] = root[x]; // ???
}

int gaseste(int x)
{
 if(x == root[x]) return x; //caz de baza
 root[x] = gaseste(root[x]); //recursie
 return root[x];
}