#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

#define MAXN 200005

int n, m;
int father[MAXN], rang[MAXN];
vector<int> ans[MAXN];
int cost, k;

struct vertex{
    int x, y, c;
} graph[MAXN];

bool compare(vertex a, vertex b)
{
    return a.c < b.c;
}

int find(int nod)
{
    while(father[nod] != nod)
        nod = father[nod];
    return nod;
}

void kruskal()
{
    for(int i = 1;i <= m;i++)
    {

        int x = find(graph[i].x), y = find(graph[i].y);
        if(x != y)
        {
            if(rang[x] < rang[y])
                father[x] = y;

            if(rang[y] < rang[x])
                father[y] = x;

            if(rang[x] == rang[y]) {
                father[x] = y;
                rang[y]++;
            }
                k++;
            ans[k].push_back(graph[i].x);
            ans[k].push_back(graph[i].y);
            cost +=  graph[i].c;
        }
    }

}

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= m; i++)
        cin >> graph[i].x >> graph[i].y >> graph[i].c;

    sort(graph+1, graph+m+1, compare);

    for(int i = 1; i <= m; i++)
    {
        father[i] = i;
        rang[i] = 1;
    }

    kruskal();

    cout << cost << "\n";
    cout << k << "\n";

    for(int i = 1; i <= k; i++)
    {
        cout << ans[i][0] << " " << ans[i][1] << "\n";
    }

}