#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAX 200001

using namespace std;

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

int n, m;
int index[MAX];
int multime[MAX];
vector <int> ans;

struct muchie
{
    int x, y;
    int cost;
}edge[MAX];

void citeste()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        edge[i].x = a;
        edge[i].y = b;
        edge[i].cost = c;
        index[i] = i;
    }
}

bool cmp(int x,int y)
{
    return (edge[x].cost < edge[y].cost);
}

int FindSet(int nod)
{
    if (multime[nod] != nod)
        multime[nod] = FindSet(multime[nod]);
    return multime[nod];
}

void uneste(int x,int y)
{
    multime[FindSet(x)] = FindSet(y);
}

int main()
{
    citeste();
    sort(index + 1,index + m + 1, cmp);
    for (int i = 1; i <= n; i++)
        multime[i] = i;
    int s = 0;
    int NrNoduri = 0;
    for (int i = 1; i <= m && NrNoduri <= n-1; i++)
    {
        if (FindSet(edge[index[i]].x) != FindSet(edge[index[i]].y))
        {
            s += edge[index[i]].cost;
            uneste(edge[index[i]].x, edge[index[i]].y);
            ans.push_back(index[i]);
        }
    }
    fout << s << "\n" << n-1 << "\n";
    for (int i = 0; i < n - 1; i++)
    {
        int p = ans[i];
        fout << edge[p].y << " " << edge[p].x << "\n";
    }
    return 0;
}