#include <iostream>
#include <bits/stdc++.h>
#define N 200005
#define M 400005
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int m[N],sz[N];
int n,k;
int sol[M],h;

struct graf
{
    int x,y,c;
};
graf a[M];

void Citire()
{
    int i,j;
    fin>>n>>k;
    for(i=1;i<=k;i++)
    {
        fin>>a[i].x>>a[i].y>>a[i].c;
        //cout<<a[i].x<<a[i].y<<"\n";
    }
    for(i=1;i<=n;i++)
    {
        m[i]=i;
        sz[i]=1;
    }

}

bool comp(graf i,graf j)
{
    return i.c<j.c; //|| i.c==j.c && i.x<j.x || i.c==j.c && i.x==j.x && i.y<j.y;
}

int Find(int val)
{
    int root=val,aux;
    while(m[root]!=root)
        root=m[root];
    while(m[val]!=root)
    {
        aux=m[val];
        m[val]=root;
        val=aux;
    }
    return root;
}
void Union(int x,int y)
{
    int root_x=Find(x);
    int root_y=Find(y);
    if(sz[root_x]<sz[root_y])
    {
        sz[root_y]+=sz[root_x];
        m[root_x]=m[root_y];
    }
    else
    {
        sz[root_x]+=sz[root_y];
        m[root_y]=m[root_x];
    }
}

void Solve()
{
    int i,CostTotal=0,w,z;

    for(i=1;i<=k && h<n-1 ;i++)
    {
        w=a[i].x;
        z=a[i].y;
       // cout<<w<<" "<<z<<"\n";
        if( Find(w) != Find(z) )
        {
            Union(w,z);
            CostTotal+=a[i].c;
            sol[++h]=i;
        }
    }
    fout<<CostTotal<<"\n";
    fout<<h<<"\n";
    for(i=1; i<=h; i++)
    {
        fout<<a[i].x<<" "<<a[i].y<<"\n";
    }
}

int main()
{
    Citire();
    sort( a+1 , a+k+1, comp );
    Solve();
    return 0;
}