#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int m,n,S,i;
bool v[200000],em[400000];
struct muchie{int a,b,c;}a[400000];
bool so(muchie A,muchie B)
{
    if(A.c<B.c)return 1;
    return 0;
}
int main()
{
    f>>n>>m;
    for(int i=0;i<m;++i)f>>a[i].a>>a[i].b>>a[i].c;
    sort(a,a+m,so);
    em[0]=1;
    v[a[0].a]=v[a[0].b]=1;
    S=a[0].c;
    for(i=1;i<m;++i)
    {
        if(v[a[i].a]!=v[a[i].b])
    {
        em[i]=1;
        v[a[i].a]=v[a[i].b]=1;
        S+=a[i].c;
        i=0;
    }
    }
    g<<S<<'\n'<<n-1<<'\n';
    for(int i=0;i<m;++i)if(em[i])g<<a[i].a<<' '<<a[i].b<<'\n';


}