#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct ceva
{
    int c,x,y;
}a[400005];
struct efectiv_ceva
{
    int x,y;
}sol[200003];
int n,m,x,y,c,t[200003],nr,solutie;
long long s;
void functie_semimagica()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].c;
    }
}
bool cmp(ceva X,ceva Y)
{
    if(X.c<Y.c)return true;
    else return false;
}
void sortare()
{
    sort(a+1,a+m+1,cmp);
}
void functia_magica_care_pregateste()
{
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }
}
void functie_de_tata_doar_partial_magica(int val,int X)
{
    while(t[X]!=X)
    {
        int c=t[X];
        t[X]=val;
        X=c;
    }
    t[X]=val;
}
void solve()
{
    functia_magica_care_pregateste();
    solutie=t[a[1].x];
    for(int i=1;i<=m;i++)
    {
        if(t[a[i].x]!=t[a[i].y])
        {
            nr++;
            s=s+a[i].c;
            sol[nr].x=a[i].x;
            sol[nr].y=a[i].y;
            if(t[a[i].x]==solutie)functie_de_tata_doar_partial_magica(t[t[a[i].x]],a[i].y);
            else functie_de_tata_doar_partial_magica(t[t[a[i].y]],a[i].x);
        }
    }
}
void scriere()
{
    g<<s<<'\n'<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<'\n';
    }
}
int main()
{
    functie_semimagica();
    sortare();
    solve();
    scriere();
    return 0;
}