#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream fout("apm.out");
int a[101][101],n,m,s[1001],ma,cost1;
struct muchie {int e1,e2,cost;};
muchie g[1001];
void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        g[i].e1=x;
        g[i].e2=y;
        g[i].cost=c;
    }

}
void kruskal()
{int i,vf;
    for(int i=1;i<=n;i++)
        s[i]=i;
        i=1;
    while(ma<n-1)
    {
        if(s[g[i].e1]!=s[g[i].e2])
        {
            ma++;
            cost1+=g[i].cost;
            vf=s[g[i].e2];
            for(int j=1;j<=n;j++)
                if(s[j]==vf)
                 s[j]=s[g[i].e1];
        }
        i++;
    }
}
void Sortare()
{
    int i,mf;
    muchie aux;
    do
    {
        mf=0;
        for(i=1;i<m;i++)
            if(g[i].cost>g[i+1].cost)
        {
            aux=g[i];
            g[i]=g[i+1];
            g[i+1]=aux;
            mf=1;
        }
    } while(mf);
}
int main()
{citire();
Sortare();
kruskal();
fout<<cost1<<'\n';
fout<<ma<<'\n';
for(int i=1;i<=ma;i++)
    fout<<g[i].e1<<" "<<g[i].e2<<'\n';




    return 0;
}