#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int viz[200001],n,m;

struct Muchie
{
    int x, y, c;
    bool operator<(const Muchie &l)const
    {
        return l.c < c;
    }
};

vector<Muchie> LA[200001];
map<int, vector<Muchie>>::iterator it;

priority_queue<Muchie> G;
priority_queue<Muchie> afisare;


void citire()
{
    Muchie M;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {

        f >> M.x >> M.y >> M.c;
        LA[M.x].push_back(M);
        LA[M.y].push_back(M);
    }

}

// bool cmp (Muchie a, Muchie b) { return a.c < b.c;}

void Adauga_Nevizitat(int x)
{
    viz[x] = 1;
    for (Muchie M:LA[x])
    {
        if (viz[M.x] + viz[M.y] == 1)
            G.push(M);
    }
}

int main()
{

    citire();
    // cout<<n<<endl;
    // for (int i =1; i<= n; i++)
    // 	{cout<<viz[i]<<" ";} cout<<endl;
    int Nod_Start = 1, Afisari = 0, cost_total = 0;
    // sort(LA.begin(), LA.end(), <);


    Adauga_Nevizitat(Nod_Start);
    // for (int i=1; i<=n; i++)
    // 	{cout<<viz[i]<<" ";} cout<<endl;
    // for (int x=1; x<=n; x++)
    //  {for (Muchie M:LA[x])
    // {
    // 	cout<<M.x<<" "<<M.y<<" "<<M.c<<endl;
    // }}
    while(G.size())
    {

        Muchie M = G.top();
        G.pop();

        if (viz[M.x] == 0 || viz[M.y] == 0)
        {
            cost_total += M.c;
            afisare.push(M);
            Afisari++;
            if (Afisari == n - 1) {
              g<<cost_total<<endl;
              g<<Afisari<<endl;
              while (afisare.size()) {
                  Muchie M = afisare.top();
                  afisare.pop();
                  g<<M.x<<" "<<M.y<<endl;
              }
            }
        }

        if (viz[M.x] == 0)
            Adauga_Nevizitat(M.x);
        if (viz[M.y] == 0)
            Adauga_Nevizitat(M.y);
        // for (int i=1; i<=n; i++)
        // {cout<<viz[i]<<" ";} cout<<endl;

    }
}