#include    <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int dim=420000;
unsigned long long cost=0;
int ans=0;
int rang[250000];

struct muchie{

    int x,y,c;

}g[dim];

struct pair{

    int prim;
    int secund;
}rez[dim];

int n,m;
int t[250000];

bool compara(muchie a,muchie b){
    if (a.c<b.c) return 1;
    return 0;
}

void citire()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        fin>>g[i].x>>g[i].y>>g[i].c;
    }
}

int radacina(int x)
{
    if (t[x]==x) return x;
    else{
        while(t[x]!=x)
        {
            x=t[x];
        }
    }
    return x;
}

void uneste(int a,int b)
{
    if (rang[a]<rang[b]) t[a]=b;
    if (rang[b]<rang[a]) t[b]=a;
    if (rang[b]==rang[a])
    {
        rang[a]++;
        t[a]=b;
    }
}


void kruskal()
{
    sort(g+1,g+1+m,compara);
    for (int i=1;i<=n;i++) {
            t[i]=i;
            rang[i]=1;
    }
    for (int i=1;i<=m && ans<n;i++)
    {
        int a=radacina(g[i].x);
        int b=radacina(g[i].y);
        if (a!=b)
        {
            cost+=g[i].c;
            rez[++ans].prim=g[i].x;
            rez[ans].secund=g[i].y;
            uneste(a,b);
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for (int i=1;i<n;i++)
    {
        fout<<rez[i].prim<<' '<<rez[i].secund<<'\n';
    }
}

int main()
{
    citire();
    kruskal();
}