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

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

#define MAXN 100005

int n, m, k;
struct vertex{
    int x, y, c;
}graph[MAXN];
int cost;
int rang[MAXN], father[MAXN];
vector<int> ans[2];

int find(int nod)
{
    while(nod != father[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[y] == rang[x])
            {
                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;

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

    kruskal();

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

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

}