//kruksal2
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
struct muchie
{
    int u,v,cost;
};
#define DIM 200001
int n,m,t[DIM],ind[DIM],ans;
muchie x[DIM];
vector<pair<int,int>>rasp;
int arbore(int nod)
{
    if(t[nod]==nod) return nod;
    t[nod]=arbore(t[nod]);
    return t[nod];
}
bool cmpf(int i,int j)
{
    return (x[i].cost<x[j].cost); 
}
void reunire(int i,int j)
{
    t[arbore(i)]=arbore(j);
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x[i].u>>x[i].v>>x[i].cost;
        ind[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }
    sort(ind+1,ind+m+1,cmpf);
    for(int i=1;i<=m;i++)
    {
        if(arbore(x[ind[i]].u)!=arbore(x[ind[i]].v))
        {
            ans+=x[ind[i]].cost;
            rasp.push_back(make_pair(x[ind[i]].u,x[ind[i]].v));
            if(rasp.size()==n-1)
            {
                break;
            }
            reunire(x[ind[i]].u,x[ind[i]].v);
        }
    }
    fout<<ans<<'\n'<<rasp.size()<<'\n';
    for(int i=0;i<rasp.size();i++)
    {
        fout<<rasp[i].first<<" "<<rasp[i].second<<'\n';
    }
}