#include <fstream>

using namespace std;

struct muchie
{
    int x,y,cost,este;
}g[100001], aux;

int n,m,c=0,k=0,v[101], ct=0;

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

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>g[i].x>>g[i].y>>g[i].cost;
        g[i].este=0;
    }
    for(int i=1;i<=n;i++)
        v[i]=i;
    for(int i=1;i<m;i++)
        for(int j=i+1;j<=m;j++)
           if(g[i].cost>g[j].cost)
        {
            aux=g[i];
            g[i]=g[j];
            g[j]=aux;
        }
    int i=1;
    while(k<n-1)
    {
        if(v[g[i].x]!=v[g[i].y])
        {
            c+=g[i].cost;
            g[i].este=1;
            ct++;
            for(int j=1;j<=n;j++)
            {
                if(v[j]==v[g[i].x] and j!=g[i].x)
                    v[j]=v[g[i].y];
            }
            k++;
            v[g[i].x]=v[g[i].y];
        }
        i++;
    }
    fout<<c<<"\n"<<ct<<"\n";
    for(int j=1;j<=m;j++)
        if(g[j].este==1)
            fout<<g[j].x<<" "<<g[j].y<<"\n";
    return 0;
}