#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

class graph
{
    public:
    int x, y, c;
};

class comp
{
    public:
    bool operator()(const graph & X, const graph & Y) const
    {
        return(X.c > Y.c);
    }
};

int N, M, v[200005], ct = 0, k = 0;
priority_queue<graph, vector<graph>, comp> Q;
queue<pair<int,int> > Sol;

void Read()
{
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        graph Gr;
        Gr.x = x;
        Gr.y = y;
        Gr.c = c;
        Q.push(Gr);
    }
}

void Initialize()
{
    for(int i = 1; i <= N; ++i)
        v[i] = i;
}

void Kruskal()
{
    while(k < N-1)
    {
        int x = Q.top().x;
        int y = Q.top().y;
        int c = Q.top().c;
        if(v[x] != v[y])
        {
            ++k;
            ct += c;
            Sol.push(make_pair(x, y));
            int q = v[x], w = v[y];
            for(int j = 1; j <= N; ++j)
                if(v[j] == w) v[j] = q;
        }
        Q.pop();
    }

}

void Read_Out()
{
    g << ct << "\n" << k << "\n";
    while(!Sol.empty())
    {
        g<< Sol.front().first << " " << Sol.front().second << "\n";
        Sol.pop();
    }
}

int main()
{
    Read();
    Initialize();
    Kruskal();
    Read_Out();
}