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

const int Nmax = 200005;

bitset <Nmax> Vizitat;
int NrNoduri, NrMuchii;

struct graf{

    int Nod, Cost;
};

list<graf>Graf[Nmax];

#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;
pair <int,int> APM[Nmax];
int Dim=0;
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[++Dim]={ans.first.first,ans.first.second};
        Vizitat[ans.first.second]=true;
        node=ans.first.second;
    }

}

void print(){

    g<<total_cost<<'\n'<<Dim<<'\n';
    for(int i=1;i<=Dim;i++)
        g<<APM[i].first<<' '<<APM[i].second<<'\n';

}

int main(){

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