#include <fstream>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x,y,cost;};
muchie M[400010],sol[400010];
int n,m,c[200010],k,ct;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>M[i].x>>M[i].y>>M[i].cost;
    }
    for(int i=1;i<=m;i++)
        for(int j=i+1;j<=m;j++)
        if(M[i].cost>M[j].cost)swap(M[i],M[j]);
    for(int i=1;i<=n;i++)c[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(c[M[i].x]!=c[M[i].y])
        {
            k++;
            int p=c[M[i].x];
            int q=c[M[i].y];
            for(int j=1;j<=n;j++)
                if(c[j]==q)c[j]=p;
            ct+=M[i].cost;
            sol[k].x=M[i].x;
            sol[k].y=M[i].y;
        }
        if(k==n-1)break;
    }
    fout<<ct<<'\n'<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        fout<<sol[i].x<<" "<<sol[i].y<<'\n';
    }
    return 0;
}