#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct nod
{
    int next,cost;
}pas;
struct heap
{
    int cost,nod;
}step;
vector<nod> H[200001],rest;
vector<nod>::iterator it;
bool uz[200001];
struct cmp
{
    bool operator()(const heap &a,const heap &b)
    {
        return a.cost>b.cost;
    }
};
priority_queue<heap,vector<heap>,cmp>Q;
int main()
{
    int n,m,i,a,tot=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>pas.next>>pas.cost;
        H[a].push_back(pas);
        swap(a,pas.next);
        H[a].push_back(pas);
    }
    for(it=H[1].begin();it!=H[1].end();it++)
    {
       step.cost=it->cost;
       step.nod=it->next;
       Q.push(step);
    }
    uz[1]=1;
    int last=1,NOD,REP;
    for(i=2;i<=n;i++)
    {
        while(uz[Q.top().nod]==1) Q.pop();
        NOD=Q.top().nod;
        REP=Q.top().cost;
        tot=tot+REP;
        pas.next=last;
        pas.cost=NOD;
        last=NOD;
        uz[NOD]=1;
        rest.push_back(pas);
        for(it=H[NOD].begin();it!=H[NOD].end();it++)
        {
            if(uz[it->next]==0)
            {
                step.cost=it->cost;
                step.nod=it->next;
                Q.push(step);
            }
        }
    }
    fout<<tot<<"\n"<<n-1<<"\n";
    for(it=rest.begin();it!=rest.end();it++) fout<<it->next<<" "<<it->cost<<"\n";
}