#include <iostream>

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

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

struct muchie
{
    int x, y, val;
};

int n, m, cnt, cost, parent[200005];
vector<muchie> v;
vector<pair<int, int>> ans;

int set_find(int x)
{
    if(x == parent[x])
        return x;
    else return parent[x] = set_find(parent[x]);
}

void dsu(int a, int b)
{
    int pa = set_find(a);
    int pb = set_find(b);

    parent[pa] = pb;
}

bool cmp(muchie a, muchie b)
{
    return a.val < b.val;
}

int main()
{
    fin >> n >> m;
    v.resize(m);
    for(int i=0; i<m; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].val;
    }
    for(int i=1; i<=n; i++)
        parent[i] = i;

    sort(v.begin(), v.end(), cmp);

    for(int i=0; i<m; i++)
    {
        if(set_find(v[i].x) != set_find(v[i].y))
        {
            cnt++;
            cost += v[i].val;
            dsu(v[i].x, v[i].y);
            ans.push_back({v[i].x, v[i].y});
        }
        if(cnt == n - 1)
            break;
    }

    fout << cost << '\n' << n - 1 << '\n';
    for(auto elm : ans)
        fout << elm.first << ' ' << elm.second << '\n';
    return 0;
}