#include <iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>
using namespace std;
//ifstream f("apm.in");
//ofstream g("apm.out");
int i,n,m,con[200001],cost,mini,maxi,sel;
bool sol[200001];
struct muchii
{
    int x,y,z;
}a[400001];

int cmp(muchii p, muchii q)
{
    return p.z < q.z;
}

void citire()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    }
}
void kruskal()
{
    for(i=1;i<=n;i++) con[i]=i; //marcam toate componentele conexe
    i=1;
    while(sel!=n-1) //cat timp nu am selectat toate cele n-1 muchii ale arborelui
    {
        if(con[a[i].x]!=con[a[i].y]) // daca nu fac parte din aceeasi comp conexa, adica nu form cicluri
        {
            sel++; //selectam varful si il adaugam in solutie
            sol[i]=1;
            cost+=a[i].z; //marim costul total
            mini=min(con[a[i].x],con[a[i].y]);
            maxi=max(con[a[i].x],con[a[i].y]);
            for(int j=1;j<=n;j++) if(con[j]==maxi) con[j]=mini; //reinitializam componenta conexa din care face arte nodul selectat, dupa unificarea celor 2 comp conexe
        }
        i++;
    }
}
void afisare()
{
    printf("%d\n%d\n",cost,n-1);
    for(i=1;i<=m;i++) if(sol[i]==1)  printf("%d %d\n",a[i].y,a[i].x);

}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(a+1,a+m+1,cmp);
    kruskal();
    afisare();
    return 0;
}