#include <bits/stdc++.h>
#define maxN 200010
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");


struct Graf{
   int x, y, c;
};
Graf G[maxN];

int multime[maxN], c;
vector<pair<int,int>> rez;

int find(int x)
{
    if(multime[x] == x)
        return x;

    multime[x] = find(multime[x]);
    return multime[x];
}


void reunion(int x, int y)
{
    multime[y] = x;
}

int main()
{

    int n, m;
    fin >> n >> m;
    for(int i=1; i<=n; i++)
        multime[i] = i;

   for(int i=1; i<=m; i++)
       fin >> G[i].x >> G[i].y >> G[i].c;

   sort(G+1, G+m+1, [](const Graf x, const Graf y){ return x.c < y.c; });

   for(int i=1; i<=m; i++){

       if(find(G[i].x) != find(G[i].y)){
           rez.push_back({G[i].x, G[i].y});
           reunion(find(G[i].x), find(G[i].y));
           c += G[i].c;
       }
   }

   fout << c << "\n";
   fout << rez.size() << "\n";
   for(auto it: rez)
        fout << it.first << " " << it.second << "\n";

    return 0;
}