#include <fstream>
#include <algorithm>
#include <iostream>

#define f first
#define s second

using namespace std;

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

int n, m, rsp, k, t[200005], fx, fy;
pair<int, int> sol[400005];
pair<int, pair<int, int> > muchi[200005];
void citire(){
    int x,y,c;
  f>> n >> m;
    for(int i = 1 ; i <= m ; i++ )
    {
        f>> x >> y >> c;
        muchi[i] = {c, {x, y}};
    }
}

int fi( int x )
{
    if(t[x] == x) return x;
    return t[x]=fi(t[x]);
}

int main()
{   int x,y,c;
citire();
    for(int i = 1 ; i <= n ; i++ )
        t[i] = i;
    sort(muchi+1, muchi+m+1);
    for(int i = 1; i <= m; ++ i)
    {
        x = muchi[i].s.f;
        y = muchi[i].s.s;
        fx = fi(x);
        fy = fi(y);
        if(fx==fy) continue;
        if(fx > fy) t[fx] = fy;
        else t[fy] = fx;

        rsp+=muchi[i].f;
        sol[++k] = {x, y};
    }
    g<< rsp << '\n' << k << '\n';
    for(int i = 1; i <= k; i++ )
        g<< sol[i].f << " " << sol[i].s << '\n';
    return 0;
}