#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

#define INF 99999999

using namespace std;

struct muchie
{
    int y, l;
}mch;

struct muchie2
{
    int x, y, l;
}MCH;

int n, m, x, y, i, l, s, a[200005];

vector <muchie> v[200005];
vector <muchie>::iterator it;
vector <int> f;
vector <int>::iterator itr;
vector <muchie2> b;
vector <muchie2>::iterator ITR;

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &l);
        mch.y=y;mch.l=l;
        v[x].push_back(mch);
        mch.y=x;
        v[y].push_back(mch);
    }

    f.push_back(1);
    a[1]=1;
    s=0;
    for(i=1;i<=n-1;i++)
    {
        MCH.l=INF;
        for(itr=f.begin();itr!=f.end();itr++)
            for(it=v[*itr].begin();it!=v[*itr].end();it++)
            {
                mch=*it;
                if(a[mch.y]==0&&mch.l<MCH.l)
                {
                    MCH.l=mch.l;
                    MCH.x=*itr;
                    MCH.y=mch.y;
                }
            }
        b.push_back(MCH);
        s+=MCH.l;
        a[MCH.y]=1;
        f.push_back(MCH.y);
    }
    printf("%d\n%d\n", s, n-1);
    for(ITR=b.begin();ITR!=b.end();ITR++)
    {
        MCH=*ITR;
        printf("%d %d\n", MCH.x, MCH.y);
    }
    return 0;
}