#include <fstream>
#include <algorithm>
#define nmax 200000
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,s,nrm,t[nmax+5],l[nmax+5];
struct numar
{
    int x,y,c;
} v[2*nmax+5],apm[nmax+5];
bool cmp(numar a,numar b)
{
    return a.c<b.c;
}
int radacina(int x)
{
    while(t[x]!=x)
        x=t[x];
    return x;
}
void join(int x,int y)
{
    int rx=radacina(x);
    int ry=radacina(y);
    if(rx==ry)
        return ;
    if(l[rx]<l[ry])
        swap(rx,ry);
    l[rx]+=l[ry];
    t[ry]=rx;

}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,cmp);
    for(int i=1; i<=n; i++)
        t[i]=i,l[i]=1;
    for(int i=1; i<=m; i++)
    {
        int  rx=radacina(v[i].x);
        int  ry=radacina(v[i].y);
        if(rx!=ry)
        {
            s+=v[i].c;
            apm[++nrm].x=v[i].x;
            apm[nrm].y=v[i].y;
            join(v[i].x,v[i].y);
        }
    }
    cout<<s<<'\n'<<nrm<<'\n';
    for(int i=1; i<=nrm; i++)
        cout<<apm[i].x<<" "<<apm[i].y<<'\n';
    return 0;
}