#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie
{
    int x;
    int y;
    int c;
};
vector <muchie> M;
vector < pair <int, int> > V;
int t[200005],n,m,i,x1,y2,c1,cost,nod1,nod2,r1,r2,marime;
bool cmp(muchie a, muchie b)
{
    return (a.c<b.c);
}
int radacina(int a)
{
    int a1=a;
    while (t[a1]!=a1) a1=t[a1];
    return a1;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d %d %d",&x1,&y2,&c1);
        muchie muchie1;
        muchie1.x=x1;
        muchie1.y=y2;
        muchie1.c=c1;
        M.push_back(muchie1);
    }
    sort(M.begin(),M.end(),cmp);
    for (i=1; i<=n; i++) t[i]=i;
    cost=0;
    for (i=0; i<m; i++)
    {
        nod1=M[i].x;
        nod2=M[i].y;
        r1=radacina(nod1);
        r2=radacina(nod2);
        if (r1!=r2)
        {
            cost+=M[i].c;
            V.push_back(make_pair(nod1,nod2));
            t[r2]=r1;
        }
    }
    printf("%d\n",cost);
    marime=V.size();
    printf("%d\n",marime);
    for (i=0; i<marime; i++) printf("%d %d\n",V[i].first, V[i].second);
    return 0;
}