#include <iostream>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
priority_queue < pair<int,pair<int,int> > ,vector < pair<int,pair<int,int> > >, greater < pair<int,pair<int,int> > > > q;
pair<int,pair<int,int> > cc;
int n,a,b,c,start,m;
long long cost;
struct nod{int info,cost;nod *urm;};
pair<int,int>  kk[200005];
nod *L[200005];
bool viz[200005];
void add(int a,int b,int cost)
{
    nod *q;
    q=new nod;
    q->info=b;
    q->cost=cost;
    q->urm=L[a];
    L[a]=q;
}

int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        fin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    nod *qq;
    qq=L[1];
    while(qq!=NULL)
    {
        q.push({qq->cost,{1,qq->info}});
        qq=qq->urm;
    }
    viz[1]=1;

    for(int i=1;i<n;i++)
    {
        cc=q.top();
        q.pop();
        while(viz[cc.second.second]==1)
        {
            cc=q.top();
            q.pop();
        }
        viz[cc.second.second]=1;
        ///tt[cc.second.second]=cc.second.first;
        cost+=cc.first;

        kk[i].first=cc.second.first;
        kk[i].second=cc.second.second;

        qq=L[cc.second.second];
        while(qq!=NULL)
        {
            if(viz[qq->info]==0)
            {
                q.push({qq->cost,{cc.second.second,qq->info}});
            }
            qq=qq->urm;
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1;i<n;i++)
        fout<<kk[i].first<<" "<<kk[i].second<<'\n';
    return 0;
}