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

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

const int NMAX = 400005;
struct muchie{
  int x,y,c;
}G[NMAX];

int n,m,tata[NMAX],rang[NMAX];
pair <int, int > sol[NMAX];
int k,cost;
bool cmp(muchie a,muchie b)
{
    return a.c < b.c;
}
void read()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
                fin >> G[i].x >> G[i].y >> G[i].c;
     for(int i = 1; i <= n; i++)
     {
         tata[i] = i;
         rang[i] = 1;
     }
     sort(G + 1,G + m + 1,cmp);
}

int Find(int nod)
{
    while(tata[nod] != nod)
        nod = tata[nod];
    return nod;
}
void Unite(int nod1,int nod2)
{
    if(rang[nod1] < rang[nod2])
        tata[nod1] = nod2;
    if(rang[nod1] > rang[nod2])
        tata[nod2] = nod1;
    if(rang[nod1] == rang[nod2])
    {
        tata[nod1] = nod2;
        rang[nod2]++;
    }
}
void solve()
{
    for(int i = 1; i <= m; i++)
    {
       int tata_x = Find(G[i].x);
       int tata_y = Find(G[i].y);
       if(tata_x != tata_y)
       {
           Unite(tata_x, tata_y);
           sol[++k].first = G[i].x;
           sol[k].second = G[i].y;
           cost = cost + G[i].c;
       }
    }
}
void afisare()
{
    fout << cost << "\n";
    fout << n - 1 << "\n";
    for(int i = 1; i <= k; i++)
        fout << sol[i].first <<" "<< sol[i].second << "\n";
}
int main()
{
    read();
    solve();
    afisare();
    return 0;
}