#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m;

struct muchii
{
    int x, y, c;
}aux;


bool cmp(muchii a, muchii b)
{
    return (a.c < b.c);
}

vector< muchii > v,arb;
vector<int> T,R;

int find(int x)
{
    int y=x;
    while(x!=T[x])
    {
        x=T[x];
    }
    T[y]=x;
    return x;
}


void join(int a, int b)
{
    int x=find(a);
    int y=find(b);
    if (R[x]<R[y]) T[x]=y; else
    if (R[x]>R[y]) T[y]=x; else
    {
        R[y]++;
        T[x]=y;
    }
}


int main()
{
    f>>n>>m;

    for(int i=0; i<=n; i++)
    {
        T.push_back(i);
        R.push_back(1);
    }

    for(int i=1; i<=m; i++)
    {
        f>>aux.x >> aux.y >> aux.c;
        v.push_back(aux);
    }

    sort(v.begin(), v.end(), cmp);


    int sum=0;

    for(int i=0; i<v.size(); i++)
    {
        if(find(v[i].x)!=find(v[i].y))
        {
            join(v[i].x, v[i].y);
            sum+=v[i].c;
            arb.push_back(v[i]);
        }
    }

    g<<sum << "\n";
    g<<arb.size() << "\n";
    for(int i=0; i<arb.size(); i++)
    {
        g << arb[i].x << " " << arb[i].y << "\n";
    }

    return 0;
}