#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
FILE*in=fopen("apm.in","r");
FILE*out=fopen("apm.out","w");
int n,m,i,x,y,val,m1=-1,ct=0,cost=0,vec;
int t[200002];
struct muchie
{
    int c,n;
};
struct muchie2
{
    int c,n1,n2;
};
struct nod
{
    int nx,ny;
};
muchie2 d;
muchie a;
nod b;
priority_queue<muchie2> p;
queue<nod> q;
vector<muchie> v[200002];
inline bool operator<(muchie2 e,muchie2 f)
{
    return e.c>f.c;
}
int main()
{
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&val);
        if(m1==-1)
        {
            t[x]=1;
            m1=x;
        }
        a.c=val;
        a.n=y;
        v[x].push_back(a);
        if(m1==x)
        {
            d.c=val;
            d.n1=x;
            d.n2=y;
            p.push(d);
        }
        a.n=x;
        v[y].push_back(a);
        if(m1==y)
        {
            d.c=val;
            d.n1=y;
            d.n2=x;
            p.push(d);
        }
    }
    while(ct<n-1)
    {
        x=p.top().n2;
        val=p.top().c;
        y=p.top().n1;
        p.pop();
        while(t[x]==1)
        {
            x=p.top().n2;
            val=p.top().c;
            y=p.top().n1;
            p.pop();
        }
        t[x]=1;
        ct++;
        b.nx=y;
        b.ny=x;
        q.push(b);
        cost=cost+val;
        for(int j=0;j<v[x].size();j++)
        {
            vec=v[x][j].n;
            val=v[x][j].c;
            if(t[vec]==0)
            {
                d.n1=x;
                d.n2=vec;
                d.c=val;
                p.push(d);
            }
        }
    }
    fprintf(out,"%d\n",cost);
    fprintf(out,"%d\n",q.size());
    while(!q.empty())
    {
        fprintf(out,"%d %d\n",q.front().nx,q.front().ny);
        q.pop();
    }
}