#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

struct muchie
{ int a,b,cost; };

class comparare
{   public:
    bool operator() (const muchie &a, const muchie &b) { return a.cost > b.cost;}
};

#define valoare_mare 500000
priority_queue<muchie, vector<muchie>, comparare> heap;
vector<muchie> muchii_posibile[valoare_mare];
vector<muchie> rezultat;
bool viz[valoare_mare];
int cost_total;

void prim(int start)
{   vector<muchie> ::const_iterator i;
    viz[start] = true;
    for (i=muchii_posibile[start].begin();i!=muchii_posibile[start].end();++i)
         heap.push(*i);
    while (!heap.empty())
    {   muchie varf = heap.top();
        heap.pop();
        if (!viz[varf.b])
         { cost_total += varf.cost;
           rezultat.push_back(varf);
           viz[varf.b] = true;
           for (i=muchii_posibile[varf.b].begin();i!=muchii_posibile[varf.b].end();++i)
                   if (!viz[i->b])
                       heap.push(*i);
         }
    }
}

int main()
{   ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {   muchie X,Y;
        f>>X.a>>X.b>>X.cost;
        Y.a=X.b;
        Y.b=X.a;
        Y.cost=X.cost;
        muchii_posibile[X.a].push_back(X);
        muchii_posibile[X.b].push_back(Y);
    }
    prim(1);
    g<<cost_total<<"\n"<<rezultat.size()<<"\n";
    for(vector<muchie> ::const_iterator i=rezultat.begin();i!=rezultat.end();++i)
        g<<i->a<<" "<<i->b<<"\n";

    return 0;
}