#include<fstream>
#include<queue>
#include<list>
#include<climits>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int Nmax = 200005;

bool Vizitat[Nmax];
int CostMinim[Nmax], Tata[Nmax], NrNoduri, NrMuchii;

struct graf{

    int Nod, Cost;
};

list<graf>Graf[Nmax];
list<graf>::iterator It;

#define type pair < pair <int,int> , int>

class cmp{
public:
    bool operator () (const type &a, const type &b) const
    {
        return a.second>b.second;
    }
};
priority_queue< type, vector< type >, cmp> pq;

void citire(){

    f >> NrNoduri >> NrMuchii;

    int nod1, nod2, cost;
    while(NrMuchii--){

        f >> nod1 >> nod2 >> cost;
        Graf[nod1].push_back({nod2, cost});
        Graf[nod2].push_back({nod1, cost});
    }
}

int total_cost;
list <pair <int,int> > APM;

void Prim(){

    int node=1;
    int nr_nodes_in_tree=1;
    Vizitat[1]=true;

    type ans;

    while(nr_nodes_in_tree<NrNoduri)
    {
        ++nr_nodes_in_tree;
        for(const auto &it:Graf[node])
            if(!Vizitat[it.Nod])
                pq.push({{node,it.Nod},it.Cost});
        ans=pq.top();
        pq.pop();
        while(Vizitat[ans.first.second])
        {
            ans=pq.top();
            pq.pop();
        }
        total_cost+=ans.second;
        APM.push_back({ans.first.first,ans.first.second});
        Vizitat[ans.first.second]=true;
        node=ans.first.second;
    }

}

void print(){

    g<<total_cost<<'\n'<<APM.size()<<'\n';
    for(const auto &it:APM)
        g<<it.first<<' '<<it.second<<'\n';

}

int main(){

    citire();
    Prim();
    print();
    return 0;
}