#include <iostream>
#include <list>
#include <utility>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct edge
{
    int s,d,c;
    edge(int s = 0, int d = 0, int c = 0):s(s),d(d),c(c){}

};
bool mycompare(const edge &a, const edge &b)
{
    return a.c < b.c;
}
vector <edge> edges;
vector <edge> solution;
int dad[200001],h[200001];
int n,m;

void Init(int i)
{
    ///avem un arbore cu un singur nod
    dad[i] = 0;
    h[i] = 0;
}
int Repr(int i)
{
    ///mergem din tata in tata pana cand dam de radacina(tatal e 0)
    while(dad[i] != 0)
    {
        i = dad[i];
    }
    return i;
}
void Union(int a, int b)
{
   ///vreau sa setez noul reprezentant pentru subarborele cu inaltimea mai mica
   int r1 = Repr(a);
   int r2 = Repr(b);
   if(h[a] > h[b])
   {
        dad[r2] = r1;
   }
   else
   {

    dad[r1] = r2;
    ///au aceeasi inaltime => se mai adauga un nivel
    if(h[a] == h[b])
        h[a] ++;
   }
}
int main()
{

    fin>>n>>m;
    for(int i = 0; i < m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        edges.push_back(edge(x,y,c));
    }
    sort(edges.begin(),edges.end(),mycompare);
    for(int i = 1; i<= n; i++)
    {
        Init(i);
    }
    int countSel = 0, cost = 0;
    for(auto &ed: edges)
    {

        if(Repr(ed.s)!=Repr(ed.d))
        {
            solution.push_back(ed);
            cost += ed.c;
            countSel ++;
            ///marchez faptul ca acum cele doua componente s-au unit - toate nodurile au acelasi reprezentant/culoare
            Union(ed.s,ed.d);
            ///solutia este gata
            if(countSel == n - 1) break;
        }

    }
    fout << cost << "\n";
    fout << solution.size() << "\n";
    for(auto &ed: solution)
    {
        fout<<ed.s << " " << ed.d << "\n";
    }
    return 0;
}