#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 200001

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

struct edge
{
    int x,y,c;
};
int n, m, cost;
vector <edge> gr, sol;
int r[Nmax];

bool cmp(edge x, edge y)
{
    return x.c<y.c;
}
int root(int x)
{
    if(r[x]==x)
        return x;
    r[x]=root(r[x]);
    return r[x];
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        edge aux;
        aux.x=x; aux.y=y; aux.c=z;
        gr.push_back(aux);
    }
    sort(gr.begin(), gr.end(), cmp);
    for(int i=1;i<=n;i++)
    {
        r[i]=i;
    }
    for(auto i:gr)
    {
        if(root(r[i.x])!=root(r[i.y]))
        {
            r[root(r[i.x])]=r[root(r[i.y])];
            sol.push_back(i);
            cost+=i.c;
        }
    }
    g<<cost<<'\n'<<sol.size()<<'\n';
    for(auto i:sol)
    {
        g<<i.x<<" "<<i.y<<'\n';
    }
    return 0;
}