#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

inline bool CMP (unsigned int X, unsigned int Y);
inline unsigned int GROUP (unsigned int node);
inline void REGROUP (unsigned int X, unsigned int Y);

unsigned int N, M;
unsigned int X[400001], Y[400001];
int C[400001];

unsigned int pos[400001], group[200001];
unsigned int i;

int sol1;
unsigned int sol2;
vector <unsigned int> sol3;

int main ()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
        fin >> X[i] >> Y[i] >> C[i];
    for (i=1; i<=M; i++)
        pos[i] = i;
    for (i=1; i<=N; i++)
        group[i] = i;
    sort(pos+1,pos+M+1,CMP);
    for (i=1; i<=M; i++)
        if (GROUP(X[pos[i]]) != GROUP(Y[pos[i]]))
        {
            sol1 += C[pos[i]];
            REGROUP(X[pos[i]],Y[pos[i]]);
            sol3.push_back(pos[i]);
        }
    sol2 = N - 1;
    fout << sol1 << '\n';
    fout << sol2 << '\n';
    for (i=0; i<sol2; i++)
        fout << X[sol3[i]] << ' ' << Y[sol3[i]] << '\n';
    return 0;
}

inline bool CMP (unsigned int X, unsigned int Y)
{
    return (C[X] < C[Y]);
}

inline unsigned int GROUP (unsigned int node)
{
    if (node == group[node])
        return node;
    group[node] = GROUP(group[node]);
    return group[node];
}

inline void REGROUP (unsigned int X, unsigned int Y)
{
    group[GROUP(X)] = GROUP(Y);
}