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

#define MAX 100000
int x[200000], y[200000], z[200000], index[200000];     //z=cost
int size[200000];
int refs[200000];
int cnt=0;
int n=0, m=0;
int partialTree[200000][3];

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

    for (int i=1;i<=m;i++)
        {in>>x[i]>>y[i]>>z[i];index[i]=i;}

    for (int i=1; i<=n; i++)
    {
        refs[i]=i;
        size[i]=1;
    }
    cnt=n;
}
void sort()
{
    int xx, yy, zz,j;
    for(int i=1;i<=m;i++)
    {
        j=i;
       // while(j>1&&edges[j][2]<edges[j-1][2])
        {
            zz=z[j];
            yy=y[j];
            xx=x[j];
            z[j]=z[j-1];
            y[j]=y[j-1];
            x[j]=x[j-1];
            z[j-1]=zz;
            y[j-1]=yy;
            x[j-1]=xx;
            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;
}

bool comp(int i,int j)
{
    return z[i]<z[j];
}

int main()
{

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

    //sort();
    sort(index+1, index+m+1, comp);
    int partialLengh=0;
    for (int i=1;i<=m;i++)
    {
        if (merge(x[index[i]],y[index[i]])==1)
        {
            partialLengh++;
            partialTree[partialLengh][0]=x[index[i]];
            partialTree[partialLengh][1]=y[index[i]];
            partialTree[partialLengh][2]=z[index[i]];
            sum+=z[index[i]];
        }
    }
    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;
    }
}


/*
int main()
{

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

    for (int i=1;i<=m;i++)
    {
        cout<<x[i]<<" "<<y[i]<<" "<<z[i]<<" "<<index[i]<<endl;
    }
    sort(index+1, index+m+1, comp);
    cout<<endl;
    for (int i=1;i<=m;i++)
    {
        cout<<x[index[i]]<<" "<<y[index[i]]<<" "<<z[index[i]]<<endl;
    }

    int partialLengh=0;
    for (int i=1;i<=m;i++)
    {
        if (merge(x[i],y[i])==1)
        {
            partialLengh++;
            partialTree[partialLengh][0]=x[index[i]];
            partialTree[partialLengh][1]=y[index[i]];
            partialTree[partialLengh][2]=z[index[i]];
            sum+=z[index[i]];
        }
    }
    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;
    }

}*/