#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, cost;
int p[100005];
struct muchie
{
    int a, b, c;
};
priority_queue <muchie> q;
vector <muchie> sol;
bool operator < (const muchie &A, const muchie &B)
{
    if(A.c == B.c)
    {
        if(A.a == B.a)
            return A.b > B.b;
        return A.a > B.a;
    }
    return A.c > B.c;
}
inline int parinte(int x)
{
    int aux;
    int r = x;
    while(p[r])
    {
        r = p[r];
    }
    while(p[x])
    {
        aux = p[x];
        p[x] = r;
        x = aux;
    }
    return r;
}
inline void Citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        muchie aux;
        fin >> aux.a >> aux.b >> aux.c;
        q.push(aux);
    }
}
inline void kruskal()
{
    while(!q.empty())
    {
        muchie aux = q.top();
        q.pop();
        int auxa, auxb;
        auxa = parinte(aux.a);
        auxb = parinte(aux.b);
        if(auxa != auxb)
        {
            p[max(auxa, auxb)] = min(auxa, auxb);
            sol.push_back(aux);
            cost += aux.c;
        }
    }
}
int main()
{
    Citire();
    kruskal();
    fout << cost << "\n" << sol.size() << "\n";
    for(auto it: sol)
        fout << it.a << " " << it.b << "\n";
    return 0;
}