#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#define NMAX 200005
std::ifstream in("apm.in");
std::ofstream out("apm.out");

using namespace std;
int n,m;
struct edge
{
    int x,y,cost;
};
int parinte[NMAX];
bool operator > (const edge a , const edge b)
{
    return (a.cost > b.cost);
}

priority_queue < edge , vector < edge > , greater < edge > > pq;
int root(int nod)
{
    if(parinte[nod] == nod)
        return nod;
    return parinte[nod] = root(parinte[nod]);
}
vector < pair < int , int > > sol;
int a,b,nr;
int main()
{
    in>>n>>m;
    for(int i=1;i<=n;i++)
    {
        parinte[i] = i;
    }
    for(int i=1;i<=m;i++)
    {
        in>>a>>b>>nr;
        pq.push({a,b,nr});
    }
    int suma = 0;
    while(!pq.empty())
    {
        if(root(pq.top().x) != root(pq.top().y))
        {
            sol.push_back({pq.top().x,pq.top().y});
            parinte[root(pq.top().x)] = root(pq.top().y);
            suma += pq.top().cost;
        }
        if(sol.size() == n-1)
        {
            break;
        }
        pq.pop();
    }
    out<<suma<<"\n";
    out<<n-1<<"\n";
    for(auto e : sol)
    {
        out<<e.first<<" "<<e.second<<"\n";
    }
    ///sort(, [](edge unu , edge doi) { return unu.cost < doi.cost ;});
    return 0;
}