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

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

using namespace std;

struct muchie
{
    int x,y,cost;
};
bool comp(muchie a,muchie b)
{
    return a.cost < b.cost;
}

vector<muchie> E,MST;
vector<int> T,H;
int N,M,Sum;

void read()
{
    fin >> N >> M;

    T.resize(N+1);
        for(int i = 1; i <= N; ++i)
            T[i] = i;
    H.resize(N+1,0);

    int x,y,c;
    for(int i = 1; i <= M; ++i)
    {
        fin >> x >> y >> c;
        E.push_back({x,y,c});
    }
}
int getT(int x)
{
    if(T[x] == x)
        return x;
    return T[x] = getT(T[x]);
}
void Kruskal()
{
    sort(E.begin(),E.end(),comp);

    int Tfirst,Tsecond,m = 0,index = 0;

    while(m < N - 1)
    {
        Tfirst = getT(E[index].x);
        Tsecond = getT(E[index].y);
        if(Tfirst != Tsecond)
        {
            ++m;
            if(H[Tfirst] > H[Tsecond])
                T[Tsecond] = Tfirst;
            else
                T[Tfirst] = Tsecond;
            if(H[Tfirst] == H[Tsecond])
                H[Tsecond]++;

            MST.push_back(E[index]);
            Sum += E[index].cost;
        }
        ++index;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);

    read();
    Kruskal();

    fout << Sum << '\n';
    fout << N - 1 << '\n';
    for(auto elem : MST)
        fout << elem.x << ' ' << elem.y << '\n';
}