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

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

struct edge
{
    int x,y,cost;
};

int cmp(edge a,edge b)
{
   return (a.cost<b.cost);
}

vector<edge> sol;
edge v[400005];
int sum;
int tata[200005];
int n,m;

int cauta(int x)
{
    if(tata[x]==x)
    {
        return x;
    }
    int k=cauta(tata[x]);
    tata[x]=k;
    return k;
}
int main()
{
    f>>n>>m;
    for(int i=0;i<n;i++)
        tata[i]=i;
    for(int i=0;i<m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    sort(v,v+m,cmp);
    for(int i=0;i<m;i++)
    {
        int x=0,y=0;
        x=cauta(v[i].x);
        y=cauta(v[i].y);
        if(x!=y)
        {
            tata[y]=x;
            sol.push_back(v[i]);
            sum+=v[i].cost;
        }
    }
    g<<sum<<"\n";
    g<<sol.size()<<"\n";
    for(int i=0;i<sol.size();i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<"\n";
    }
    return 0;
}