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

#define MAX 100000
int edges[100][3];
int size[100];
int refs[100];
int cnt=0;
int n=0, m=0;
int partialTree[100][3];

void initialize()
{
    ifstream in ("apm.in");
    in>>n>>m;

    for (int i=1;i<=m;i++)
        in>>edges[i][0]>>edges[i][1]>>edges[i][2];

    for (int i=1; i<=n; i++)
    {
        refs[i]=i;
        size[i]=1;
    }
    cnt=n;
}
void sort()
{
    int x, y, z,j;
    for(int i=1;i<=m;i++)
    {
        j=i;
        while(j>1&&edges[j][2]<edges[j-1][2])
        {
            x=edges[j][2];
            y=edges[j][1];
            z=edges[j][0];
            edges[j][2]=edges[j-1][2];
            edges[j][1]=edges[j-1][1];
            edges[j][0]=edges[j-1][0];
            edges[j-1][2]=x;
            edges[j-1][1]=y;
            edges[j-1][0]=z;
            j--;
        }
    }
}


int find(int p)
{
    int root = p;
    while (root != refs[root])
        root = refs[root];
    while (p != root) {
        int newp = refs[p];
        refs[p] = root;
        p = newp;
    }
    return root;
}


int merge(int x, int y)
{
    int i = find(x);
    int j = find(y);
    //cout<<"se compara "<<i<<" cu "<<j;
    if (i == j) return 0;

    if   (size[i] < size[j])
    {
        refs[i] = j;
        size[j] += size[i];
    }
    else
    {
        refs[j] = i;
        size[i] += size[j];
    }
    cnt--;
    return 1;
}

int main()
{
    /*int sum=0;        //versiunea de consola
    initialize();

    for (int i=1;i<=m;i++)
    {
        cout<<edges[i][0]<<" "<<edges[i][1]<<" "<<edges[i][2]<<endl;
    }
    sort();
    cout<<endl;
    for (int i=1;i<=m;i++)
    {
        cout<<edges[i][0]<<" "<<edges[i][1]<<" "<<edges[i][2]<<endl;
    }

    int partialLengh=0;
    for (int i=1;i<=m;i++)
    {
        if (merge(edges[i][0],edges[i][1])==1)
        {
            partialLengh++;
            partialTree[partialLengh][0]=edges[i][0];
            partialTree[partialLengh][1]=edges[i][1];
            partialTree[partialLengh][2]=edges[i][2];
            sum+=edges[i][2];
        }
    }
    cout<<endl<<"Costul arborelui este de:"<<sum;
    cout<<endl<<"Dimensiunea arborelui este de:"<<partialLengh;
    cout<<endl<<"Arborele partial obtinut este format din laturile:"<<endl;
    for (int i=1;i<=partialLengh;i++)
    {
        cout<<partialTree[i][0]<<" "<<partialTree[i][1]<<" de lungime "<<partialTree[i][2]<<endl;
    }*/


    int sum=0;        //versiunea de infoarena
    initialize();

    sort();

    int partialLengh=0;
    for (int i=1;i<=m;i++)
    {
        if (merge(edges[i][0],edges[i][1])==1)
        {
            partialLengh++;
            partialTree[partialLengh][0]=edges[i][0];
            partialTree[partialLengh][1]=edges[i][1];
            partialTree[partialLengh][2]=edges[i][2];
            sum+=edges[i][2];
        }
    }
    ofstream out("apm.out");
    out<<sum<<endl;
    out<<partialLengh<<endl;
    for (int i=1;i<=partialLengh;i++)
    {
        out<<partialTree[i][0]<<" "<<partialTree[i][1]<<endl;
    }
}