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

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

const int dim=400001;
int cost=0;
int ans=0;
int rang[200001];
int aux=0;

struct muchie{

    int x,y,c;

}g[dim];

struct pair{

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

int n,m;
int t[200005];

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){
    t[x]=radacina(t[x]);
   }
   return t[x];
}

void uneste(int x,int y)
{
    if (rang[x]<rang[y])
    {
        t[x]=y;
    }
    else
        if (rang[x]>rang[y]) t[y]=x;
    else
    if (rang[x]==rang[y]){
        t[x]=y;
        rang[x]++;
    }
}


void kruskal()
{
    sort(g+1,g+1+m,compara);
    for (int i=1;i<=n;i++) {
            t[i]=i;
    }
    for (int i=1;i<=m && aux<n;i++)
    {
        int a=radacina(g[i].x);
        int b=radacina(g[i].y);
        if (a!=b)
        {
            uneste(a,b);
            cost+=g[i].c;
            rez[++ans].prim=g[i].x;
            rez[ans].secund=g[i].y;
            aux++;
        }
    }
    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();
}