#include <iostream>
#include <fstream>
#include <queue>
#include <set>

using namespace std;

struct muchie{
int x,y,c;
}k;

bool operator<(const muchie &a, const muchie &b)
{
    if(a.c!=b.c)
    return a.c < b.c;
    else
    return 1;
}

set <struct muchie> s;
set <struct muchie>::iterator it;

int viz[50001],tata[50001];

int main()
{
int n,m,i,a,b,d,l,cmin,aux;
ifstream f("apm.in");
ofstream g("apm.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
    f>>a>>b>>d;
    k.x=a; k.y=b; k.c=d;
    s.insert(k);
    k.x=b;
    k.y=a;
    s.insert(k);
}

k=*s.begin();
viz[k.x]=viz[k.y]=1;
tata[k.y]=k.x;
cmin=k.c;
s.erase(s.begin());
for(l=2;l<=n-1;l++)
{
    for(it=s.begin();it!=s.end();++it)
    {
        if(viz[it->x]==1&&viz[it->y]==1)
            s.erase(it);
        if(viz[it->x]==1&&viz[it->y]==0)
        {
            viz[it->y]=1;
            tata[it->y]=it->x;
            cmin+=it->c;
            s.erase(it);
            break;
        }
    }
}
g<<cmin<<'\n'<<n-1<<'\n';
for(i=1;i<=n;i++)
    if(tata[i]!=0)
    g<<i<<" "<<tata[i]<<'\n';
return 0;
}