#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

ifstream fin("apm.in"); /// parc.in
ofstream fout("apm.out"); /// parc.in
int n, m, c, x, y, vt[100001], a, b, cs;
pair<int, pair <int, int> > v[200000];
vector <pair<int, int> > vc;

int main()
{
    fin>>n>>m;
    for(int i = 1; i<=m; i++)
    {
        fin>>x>>y>>c;
        v[i] = {c,{x, y}};
    }
    sort(v+1, v+m+1);
    for(int i=1; i<=m; i++)
    {
        x = v[i].second.first;
        y = v[i].second.second;
        c = v[i].first;

        a = x;
        b = y;
        while(vt[a] != 0)
            a = vt[a];
        while(vt[b] != 0)
            b = vt[b];

        int a1 = x;
        int b1 = y;
        while(vt[a1] != 0)
        {
            int t = vt[a1];
            vt[a1] = a;
            a1 = t;
        }
        while(vt[b1] != 0)
        {
            int t = vt[b1];
            vt[b1] = b;
            b1 = t;
        }

        if(a != b){
            vt[b] = a;
            cs += c;
            vc.push_back({x, y});
        }
    }
    fout<<cs<<endl<<vc.size()<<endl;
    for(auto x:vc)
        fout<<x.first<<' '<<x.second<<endl;
}