#include <cstdio>
#define NMAX 200100
#include <queue>
using namespace std;
int tata[NMAX], h[NMAX];
int n,m;
double cmin;
struct muchie{ int x;
               int y;
               double c;
               friend bool operator <(const muchie &a, const muchie &b);
};
vector<muchie> apm;
bool operator >(const muchie &a, const muchie &b)
{
    return a.c>b.c;
}
priority_queue<muchie, vector<muchie>, greater<muchie> > Q;
int grupa(int x)
{
    int rx=x,y;
    while(tata[rx]) rx=tata[rx];
    while(x!=rx)
    {
        y=tata[x];
        tata[x]=rx;
        x=y;
    }
    return rx;
}
void reuniune(int i, int j)
{
    int rx, ry;
    rx=grupa(i);
    ry=grupa(j);
    if(h[rx]>h[ry])
        tata[ry]=rx;
    else
        tata[rx]=ry;
    if(h[rx]==h[ry])
        h[ry]++;
}
void citire()
{
    int i;
    muchie crt;
    scanf("%d%d", &n, &m);
    for(i=0;i<m;++i)
    {
        scanf("%d%d%lf", &crt.x, &crt.y, &crt.c);
        Q.push(crt);
    }
}
void afisare()
{
    int i;
    printf("%.0lf\n%d\n", cmin, n-1);
    for(i=0;i<n-1;++i)
        printf("%d %d\n", apm[i].x, apm[i].y);
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    citire();
    muchie crt;
    int nrsel=0, rx, ry;
    while(nrsel<n-1)
    {
        crt=Q.top(); Q.pop();
        rx=grupa(crt.x);
        ry=grupa(crt.y);
        if(rx!=ry)
        {
            cmin+=crt.c;
            reuniune(rx, ry);
            apm.push_back(crt);
            ++nrsel;
        }
    }
    afisare();
    return 0;
}