#include <fstream>
#include <algorithm>

#define f first
#define s second

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

int n, m, x, y, c, rsp, k, t[200005], fx, fy;
pair<int, int> sol[400005];
pair<int, pair<int, int> > muchii[200005];

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

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

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