#include <fstream>///Kruskal
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

const int maxn = 400002;
struct graf {int nod1, nod2, cost;} A[maxn];
int n, m, S;
vector < int > T, Sol;

void Citire()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m; ++ i)  cin >> A[i].nod1 >> A[i].nod2 >> A[i].cost;
    T.resize(n+1);
    for(int i = 1; i <= n; ++ i) T[i] = i;
    Sol.resize(n);
}

void Afisare()
{
    cout << S << '\n';
    cout << n - 1 << '\n';
    for(int i = 1; i < n; ++ i) cout << A[Sol[i]].nod1 << ' ' << A[Sol[i]].nod2 << '\n';
}

bool fx(graf x, graf y) { return x.cost < y.cost; }

int Tata(int x)
{
    if(T[x] != x) T[x] = Tata(T[x]);
    return T[x];
}

void APM()
{
    sort(A + 1, A + m + 1, fx);
    int k = 0,i = 1;
    while(k < n-1)
    {
        int t1 = Tata(A[i].nod1);
        int t2 = Tata(A[i].nod2);
        if(t1 != t2)
        {
            S += A[i].cost;
            T[t2] = t1;
            Sol[++k] = i;
        }
        ++ i;
    }
}

int main()
{
    Citire();
    APM();
    Afisare();
}