#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
int n, m;
struct muchie
{
    int x, y, cost;
} v[400005], pivot;
int c[200005], a[400005];
void initializare()
{
    int i;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>v[i].x>>v[i].y>>v[i].cost;
    }
    for(i=1; i<=n; i++)
        c[i]=i;
}
void sortaremuchii(int st, int dr)
{
    int i, j, k;
    if(st<dr)
    {pivot=v[st]; i=st, j=dr;
    while(i<j)
    {
        while(i<j && v[j].cost>=pivot.cost) j--;
        v[i]=v[j];
        while(i<j && v[i].cost<=pivot.cost) i++;
        v[j]=v[i];
    }
    v[i]=pivot;
    sortaremuchii(st, i-1);
    sortaremuchii(i+1, dr);
    }
}
void afisare(int msel)
{
    int i, cost=0;
    for(i=1; i<n; i++)
        cost+=v[a[i]].cost;
    g<<cost<<"\n"<<msel<<"\n";
    for(i=1; i<n; i++)
        g<<v[a[i]].y<<" "<<v[a[i]].x<<"\n";
}
int main()
{
    int i, minn, maxx, msel, j;
    initializare();
    sortaremuchii(1, m);
    msel=0;
    for(i=1; msel<n-1; i++)
    {
        if(c[v[i].x]!=c[v[i].y])
        {
            msel++;
            a[msel]=i;
            if(c[v[i].x]<c[v[i].y])
            {
                minn=c[v[i].x];
                maxx=c[v[i].y];
            }
            else
            {
                minn=c[v[i].y];
                maxx=c[v[i].x];
            }
            for(j=1; j<=n; j++)
                if(c[j]==maxx) c[j]=minn;
        }
    }
    afisare(msel);
    return 0;
}