#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct muchie
{
    int x, y, c;
    bool operator()(muchie a, muchie b)
    {
        return a.c > b.c;
    }
};

priority_queue<muchie, vector<muchie>, muchie> q;
vector<muchie> sol;
int n, m;

int tat[200010];

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

int isConected(int x, int y)
{
    return parent(x) == parent(y);
}

int conect(int x, int y)
{
    tat[x] = y;
}

void kruskal()
{
    int sum = 0;
    while (!q.empty() && sol.size() < n-1)
    {
        muchie aux = q.top();
        q.pop();
        if (isConected(aux.x, aux.y))
            continue;
        sol.push_back(aux);
        conect(parent(aux.x), parent(aux.y));
        sum += aux.c;
    }
    printf("%d\n%d\n", sum, sol.size());
    for (int i = 0; i < sol.size(); i++)
        printf("%d %d\n", sol[i].y, sol[i].x);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        q.push({x, y, c});
    }
    for (int i = 1; i <= n; i++)
        tat[i] = i;
    kruskal();
    /*while(!q.empty())
    {
        cout << q.top().x << " " << q.top().y << " " << q.top().c << "\n";
        q.pop();
    }*/

    return 0;
}