#include <stdio.h>
#include<vector>
#include<map>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include <iostream>
using namespace std;

vector < vector< pair <long,long> > > graf;
vector< pair <long,long> > tmp;
multimap < long,pair <long,long> > V;
long nr[200001],comp[200001];
static long n,m,i,j,x,y,z,t,te;
long coada[200000],len;
inline static long CM(long &x)
{
    te=x;
    while (comp[te]!=te)
    {
        coada[len++]=te;
        te=comp[te];
    }
    while (len>0)
    {
        comp[coada[len]]=te;
        len--;
    }
    return te;
}
inline void link (long &x, long &y)
{
    nr[comp[x]]+=nr[comp[y]];
    comp[CM(y)]=comp[CM(x)];
}
inline void kruskal()
{
    t=n-1;
    pair <long,long> u;
    queue < pair<long,long> > coada;
    long t1,t2,cost,sum;
    sum=0;
    len=0;
    while (t>0)
    {
        cost=(*V.begin()).first;
        u=(*V.begin()).second;
        V.erase(V.begin());
        t1=CM(u.first);
        t2=CM(u.second);
        if (t1!=t2)
        {
            sum+=cost;
            coada.push(u);
            if (nr[t1]>=nr[t2])
                link(u.first,u.second);
            else
                link(u.second,u.first);
            t--;
        }
    }
    printf ("%ld\n%ld\n",sum,n-1);
    while (coada.size()>0)
    {
        printf ("%ld %ld\n",coada.front().first,coada.front().second);
        coada.pop();
    }
}
char a[101],b;
long asd,k,s;
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf ("%ld%ld",&n,&m);
    for (i=0;i<=n;i++)
        comp[i]=i,nr[i]=1;
    scanf ("%c",&b);
    for (i=1;i<=m;i++)
    {
        //scanf ("%ld%ld%ld",&x,&y,&z);
        fgets(a, 100, stdin);
        k=strlen(a);
        x=y=z=-1;
        asd=0;
        s=1;

        for (j=0;j<=k;j++)
        {
            if (a[j]=='-')
            {
                s=-1;
            }
            else
            if (a[j]==' '||a[j]==0||a[j]=='\n')
            {

                if (x==-1)
                    x=asd*s;
                else
                    if (y==-1)
                        y=asd*s;
                    else
                    {
                        z=asd*s;
                        break;
                    }
                asd=0;
                s=1;
            }
            else
                asd=asd*10+a[j]-'0';
        }
        V.insert(make_pair(z,make_pair(x,y)));
    }
    kruskal();
    return 0;
}