#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct muchie{int x,y,cost;}c[400001];
int n,m,cc[200001],z,v[200001],cost;

bool cmp(muchie q,muchie w)
{
    if(q.cost>w.cost) return false;
    return true;
}

void afisare_cc(){for(int i=1; i<=n; i++) fout<<cc[i]<<" ";fout<<endl;}
void afisare_c(){for(int i=1; i<=m; i++) fout<<c[i].x<<" "<<c[i].y<<" "<<c[i].cost<<endl; fout<<endl;}

int main()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m;i++)
        fin>>c[i].x>>c[i].y>>c[i].cost;
    //afisare_c();

    for(i=1; i<=n; i++)cc[i]=i;
    sort(c+1,c+m+1,cmp);
    //afisare_c();

    int k=1,nr=1;
    while (nr<n)
    {
        int x=c[k].x;
        int y=c[k].y;
        if(cc[x]!=cc[y]){
            int val=cc[y];
            z++;
            v[z]=k;
            cost+=c[k].cost;
            for(int i=1; i<=n; i++)
             if(cc[i]==val) cc[i]=cc[x];
           // afisare_cc();
            nr++;
        }
        k++;
    }

    fout<<cost<<endl<<z<<endl;
    for(i=1; i<=z; i++)fout<<c[v[i]].x<<" "<<c[v[i]].y<<endl;
    return 0;
}