#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#define mod 666013

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{int cost,x,y;} v[400005],M;
int n,m,i,j,sol[400005],father[200005],rang[200005],cnt,sum;

bool cmp(muchie a, muchie b)
{
    return a.cost<b.cost;
}

void update(int x, int y)
{
    int f1=x,f2=y;
    while(father[f1]) f1=father[f1];
    while(father[f2]) f2=father[f2];
    if(rang[f1]>rang[f2])
    {
        father[f2]=f1;
    }
    else if(rang[f1]==rang[f2])
    {
        father[f2]=f1;
        rang[f1]++;
    }
    else father[f1]=f2;
}

void join(int x)
{
    int f,aux;
    f=x;
    while(father[f]) f=father[f];
    while(x!=f && father[x]!=f)
    {
        aux=father[x];
        father[x]=f;
        x=aux;
    }
}

bool query(int x, int y)
{
    join(x);
    join(y);
    while(father[x]) x=father[x];
    while(father[y]) y=father[y];
    if(x==y) return 1;
    return 0;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++) f>>v[i].x>>v[i].y>>v[i].cost;
    for(i=1;i<=n;i++) rang[i]=1;
    sort(v+1,v+m+1,cmp);
    cnt=0; i=1; sum=0;
    while(cnt<n-1)
    {
        M=v[i];
        if(!query(M.x,M.y))
        {
            update(M.x,M.y);
            sol[i]=1;
            sum+=M.cost;
            cnt++;
        }
        i++;
    }
    g<<sum<<'\n'<<n-1<<'\n';
    for(i=1;i<=m;i++) if(sol[i]) g<<v[i].x<<' '<<v[i].y<<'\n';
    return 0;
}