#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int maxn = 200005;
vector <pair <int, int> > ans;
int F[maxn];

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

input muchii[maxn * 2];
vector <int> v[maxn];

inline bool cmp(input a, input b)
{
    if(a.cost != b.cost)
        return a.cost < b.cost;
    if(a.x != b.x)
        return a.x < b.x;
    return a.y <= b.y;
}

int rad(int x)
{
    if(F[x] < 0)
        return x;
    return rad(F[x]);
}

void join(int x, int y)
{
    x = rad(x);
    y = rad(y);
    if(-F[x] < -F[y])
    {
        F[y] = F[y] + F[x];
        F[x] = y;
    }
    else
    {
        F[x] = F[x] + F[y];
        F[y] = x;
    }
}

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
        in >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
    sort(muchii + 1, muchii + m + 1, cmp);
    int sum = 0;
    for(int i = 1; i <= n; i++)
        F[i] = -1;
    for(int i = 1; i <= m; i++)
    {
        int nodx = muchii[i].x;
        int nody = muchii[i].y;
        if(rad(nodx) != rad(nody))
        {
            join(nodx, nody);
            sum = sum + muchii[i].cost;
            ans.push_back(make_pair(nodx, nody));
        }
    }
    out << sum << "\n" << ans.size() << "\n";
    for(auto it : ans)
        out << it.first << " " << it.second << "\n";
    return 0;
}