#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
struct muchii
{
    int x;
    int y;
    int c;
}mch[400002];
int p[200002];
int rang[200002];
struct solutie
{
    int x0;
    int y0;
}sol[200002];
bool comp(struct muchii a,struct muchii b)
{
    return a.c<b.c;
}
inline void create_set(int i)
{
    p[i]=i;
    rang[i]=0;
}
int find_set(int i)
{
    if(p[i]!=i)
        p[i]=find_set(p[i]);
    return p[i];
}
int merge_set(int a,int b)
{
    int aroot=find_set(a);
    int broot=find_set(b);
    if(aroot==broot)
        return 0;
    else{
        if(rang[aroot]>rang[broot])
        {
            p[broot]=aroot;
        }
        else if(rang[aroot]<rang[broot])
        {
            p[aroot]=broot;
        }
        else
        {
            p[broot]=aroot;
            rang[aroot]++;
            return 1;
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>mch[i].x>>mch[i].y>>mch[i].c;
    }
    //sortam
    sort(mch+1,mch+m+1,comp);
    //punem nodurile in multime diferita
    for(int i=1;i<=n;i++)
        create_set(i);
    //kruskal
    int nrmuchii=0;
    int cost=0;
    for(int i=1;i<=m && nrmuchii<n-1;i++)
    {
        if(merge_set(mch[i].x,mch[i].y))
        {
            cost+=mch[i].c;
            nrmuchii++;
            sol[nrmuchii].x0=mch[i].x;
            sol[nrmuchii].y0=mch[i].y;
        }
    }
    g<<cost<<"\n"<<nrmuchii<<"\n";
    for(int i=1;i<=n-1;i++)
    {
        g<<sol[i].x0<<" "<<sol[i].y0<<"\n";
    }
    return 0;
}