#include <bits/stdc++.h>
#define N_MAX 100005

using namespace std;

ifstream fin("apm.in");

ofstream fout("apm.out");

vector<pair<int, int>> sol;

struct nod
{
    int x, y, cost;
} l[N_MAX];

int tata[N_MAX];

int n, m;
int lng[N_MAX];
bool compara(nod a, nod b)
{
    return a.cost < b.cost;
}

int getroot(int x)
{
    while (tata[x] != x)
        x = tata[x];
    return x;
}
int main()
{
    fin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int i, j, cost;
        fin >> i >> j >> cost;
        l[k] = {i, j, cost};
    }
    for (int i = 1; i <= n; i++)
        tata[i] = i;
    sort(l + 1, l+m+ 1, compara);
    long long int rez = 0;
    for (int i = 1; i <= m; i++)
    {
        if (getroot(l[i].x) != getroot(l[i].y))
        {
            rez += l[i].cost;
            int a = l[i].x;
            int b = l[i].y;
            sol.push_back({a, b});
            a=getroot(a);
            b=getroot(b);
            if(lng[a]<lng[b])
            swap(a,b);
            tata[b] = a;
            lng[a]+=lng[b];
            
        }
    }
    fout << rez << '\n'
         << (n - 1)<<'\n';
    for (int i = 1; i <= n - 1; i++)
        fout << sol[i-1].first << " " << sol[i-1].second << '\n';
}