#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int grup[200001];

int whoIsDaddy(int startnode)
{
    int current = startnode;
    vector<int>passedby;

    while(grup[current] != current)
    {
        passedby.push_back(current);
        current = grup[current];
    }

    for(auto node:passedby)
    {
        grup[node] = current;
    }

    return current;
}

void makeHimMyDaddy(int newDaddy,int DaddysNewToy){

    int root = whoIsDaddy(DaddysNewToy);
    grup[root] = whoIsDaddy(newDaddy);
}


struct muchie{
    int node1,node2,cost;
};

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

vector<muchie>muchii;

int main()
{
    int n,m,i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        grup[i]=i;
    }

    for(i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        muchii.push_back({a,b,c});
    }

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

    vector<pair<int,int>>v;
    int sum = 0;

    for(auto muc:muchii)
    {
        if(whoIsDaddy(muc.node1) != whoIsDaddy(muc.node2))
        {
            sum+=muc.cost;
            v.push_back(make_pair(muc.node1,muc.node2));
            makeHimMyDaddy(muc.node1,muc.node2);
        }
    }

    cout<<sum<<'\n';
    cout<<v.size()<<'\n';
    for(auto buc:v)
    {
        cout<<buc.first<<" "<<buc.second<<'\n';
    }

    return 0;
}