#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int nmax=200000;
const int mmax=400000;
struct muchie
{
    int a,b,cost;
};
bool operator <(muchie a,muchie b)
{
    return a.cost<b.cost;
}
int n,m;
muchie v[nmax+5];
int t[nmax+5];
int h[nmax+5];
int FindSet(int nod)
{
    while(nod!=t[nod])
        nod=t[nod];
    return nod;
}
int UniteSet(int x,int y)
{
    if(h[x]==h[y])
    {
        h[x]++;
        t[y]=x;
    }
    else
        if(h[x]>h[y])
            t[y]=x;
        else
            t[x]=y;

}
struct info
{
    int a,b;
};
vector<info>sol;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].cost);
    }
    sort(v+1,v+m+1);
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    int ans=0;
    for(int i=1;i<=m;i++)
    {
       /// cout<<v[i].a<<" "<<v[i].b<<" , "<<v[i].cost<<"\n";
        int x,y;
        x=FindSet(v[i].a);
        y=FindSet(v[i].b);
        if(x!=y)
        {
            sol.push_back({v[i].a,v[i].b});
            UniteSet(x,y);
            ans+=v[i].cost;
        }
    }
    printf("%d\n%d\n",ans,sol.size());
    for(int i=0;i<sol.size();i++)
        printf("%d %d\n",sol[i].a,sol[i].b);
    return 0;
}
/**
**/