#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod{
    int x,y,c;
};
vector<nod>v;
vector<nod>sol;
int rang[200010],t[200010];
int n,cost,nr,m;
bool cmp(nod a,nod b)
{
    return a.c < b.c;
}
int radacina(int k)
{
    if(t[k]==0)
        return k;
    int x=radacina(t[k]);
    t[k]=x;
    return x;
}
void uneste(int x,int y)
{
    int rx=radacina(x), ry=radacina(y);
    if(rang[rx] > rang[ry])
        t[ry]=rx;
    else if(rang[rx] < rang[ry])
        t[rx]=ry;
    else
    {
        t[ry]=rx;
        rang[rx]++;
    }
}
int main() {
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        nod x;
        f>>x.x>>x.y>>x.c;
        v.push_back(x);
    }
    sort(v.begin(),v.end(),cmp);
    for(auto it:v)
        if(radacina(it.x) != radacina(it.y))
        {
            cost+=it.c;
            nr++;
            uneste(it.x, it.y);
            sol.push_back(it);
            if(nr == n-1)
                break;
        }
    g<<cost<<'\n'<<n-1<<'\n';
    for(auto it:sol)
        g<<it.x<<' '<<it.y<<'\n';
    return 0;
}