#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define inf 999999
#define pq priority_queue

using namespace std;

struct muchie
{
    int x,y,cost;
};

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

pq<muchie, vector<muchie>, comparare> hp;
vector<muchie> muchp[inf];
vector<muchie> rez;
bool viz[inf];
int cost_total;

void prim(int start)
{   vector<muchie> ::const_iterator i;
    viz[start] = true;
    for (i=muchp[start].begin();i!=muchp[start].end();++i)
         hp.push(*i);
    while (!hp.empty())
    {   muchie varf = hp.top();
        hp.pop();
        if (!viz[varf.y])
         { cost_total += varf.cost;
           rez.push_back(varf);
           viz[varf.y] = true;
           for (i=muchp[varf.y].begin();i!=muchp[varf.y].end();++i)
                   if (!viz[i->y])
                       hp.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.x>>X.y>>X.cost;
        Y.x=X.y;
        Y.y=X.x;
        Y.cost=X.cost;
        muchp[X.x].push_back(X);
        muchp[X.y].push_back(Y);
    }
    prim(1);
    g<<cost_total<<"\n"<<rez.size()<<"\n";
    for(vector<muchie> ::const_iterator i=rez.begin();i!=rez.end();++i)
        g<<i->x<<" "<<i->y<<"\n";

    return 0;
}