#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
int n,m,nr,sum;
int parinti[10005];
struct muchie
{
    int noda,nodb,val;
}a[10005];
vector <muchie> muchii;
bool compara(muchie a, muchie b)
{
    return a.val<b.val;
}
void Union(int a,int b)
{
    parinti[a]=b;
}
int Find(int nod)
{
    int copie_nod=nod;
    while (parinti[nod])nod=parinti[nod];
    while (parinti[copie_nod])
    {
        int aux=copie_nod;
        copie_nod=parinti[copie_nod];
        parinti[aux]=nod;
    }
    return nod;
}
int main()
{
    cin >> n >> m;
    for (int i=1;i<=m;i++)
    {
        int x,y,val;
        cin >> x >> y >> val;
        a[i].noda=x;
        a[i].nodb=y;
        a[i].val=val;
    }
    sort(a+1,a+m+1,compara);
    for (int i=1;i<=m;i++)
    {
        int x=a[i].noda;
        int y=a[i].nodb;
        int parinte1=Find(x);
        int parinte2=Find(y);
        if (parinte1!=parinte2)
        {
            nr++;
            Union(parinte1,parinte2);
            sum+=a[i].val;
            muchii.push_back(a[i]);
        }
        if (nr==n-1) break;
    }
    cout << sum << '\n' << n-1 << '\n';
    for (int i=0;i<nr;i++)
    {
        cout << muchii[i].noda << " " << muchii[i].nodb << '\n';
    }
    return 0;
}