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

const int NMAX = 200200;

int r[NMAX], k[NMAX];
int n, m;
int X[NMAX], Y[NMAX], C[NMAX];
vector<int> indice;
vector<int> arbore;
void MakeSet(int n) // formeaza multimi cu un singur element
{
    for(int i = 0 ; i <= n; i++)
    {
        r[i] = i;//vector de reprezentanti
        k[i] = 0;//multimea fiecarui varf , initial arbore
}
}
int FindSet(int u)
{
    int p, v;
   for(p = u; r[p] != p; p = r[p]); //drumul de căutare de la u la rădăcină
    //compresie de cale
while(r[u] != u)
    {
        v = r[u];
        r[u] = p;
        u=v;
    }
    return p;
}
bool Union(int u, int v) //reunește mulțimea care conține elementul u cu cea care conține elementul v
{
    if(u == v)
return false;
    if(k[u] > k[v])
    r[v] = u;
    else
    r[u] = v;
    if(k[u] == k[v])
     k[v]++;
     return true;
}
bool pred(int u, int v)
{
return C[u] < C[v];
}
int main()
{
    ifstream f("apm.txt");
    ofstream g("apm.out");
    int cost = 0;
    f>>n>>m;
    MakeSet(n);
    indice.push_back(-1);
    for(int i = 1; i <= m; i++)
    {
     int a,b,c;
     f>>a>>b>>c;
     X[i] = a;
     Y[i] = b;
     C[i] = c;
     indice.push_back(i);
}
    sort(indice.begin()+1, indice.begin()+m+1, pred); //sortează muchiile grafului crescător după costuri
    for(int i = 1; i <= m; i++)
     {
      if(Union(FindSet(X[indice[i]]), FindSet(Y[indice[i]])))
{
     arbore.push_back(indice[i]);
      cost += C[indice[i]];
      }
       }
     g<<cost<<'\n'<<n-1<<'\n';
    for(unsigned int i = 0; i < arbore.size(); i++)
    g<<X[arbore[i]]<<' '<<Y[arbore[i]]<<'\n';
    return 0;
}