#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 200005
#define MMAX 400005
using namespace std;

struct muc
{
   int c,x,y;

}a[MMAX],muchie;

int n,m,x,y,c,nrM,cost;
int arbore[NMAX],C[NMAX],R[NMAX];

int find_union(int x)
{
    int r,aux;
    for(r=x;C[r]!=r;r=C[r]);

    for(;x!=C[x];)
    {
        aux = C[x];
        C[x] = r;
        x=aux;
    }
    return r;
}

void unite_union(int r1,int r2)
{
    if(R[r1]>R[r2])
        C[r2] = r1;
    else
        C[r1] = r2;
    if(R[r1]==R[r2]) R[r2]++;
}

bool pred(muc a,muc b)
{
    if(a.c < b.c)
        return true;
    else
        return false;

}


int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> n >> m;
    for(int i=1;i<=m;i++)
    {
        in >> x >> y >> c;
        muchie.x = x;
        muchie.y = y;
        muchie.c = c;
        a[i] = muchie;
    }
    sort(a+1,a+m+1,pred);

    for(int i=1;i<=n;i++)
    {
        C[i]=i;
        R[i]=0;
    }
    for(int i=1; nrM<n-1; i++)
    {
        if(find_union(a[i].x)!= find_union(a[i].y))
           {
               arbore[++nrM] = i;
              // cout << a[i].c << endl;
               cost = cost + a[i].c;
               unite_union(find_union(a[i].x),find_union(a[i].y));
           }
    }
    out << cost << "\n" << nrM << "\n";
    for(int i=1;i<=nrM;i++)
        out << a[arbore[i]].x << " " << a[arbore[i]].y << "\n";
    return 0;
}