#include <fstream>
#include <algorithm>

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

const int maxN = 200001;
const int maxM = 400001;

int N, M;

struct disjoint_set {
    int parent;
    int rank_ = 0;
}V[maxN];

int rootOf(int i)
{
    if(V[i].parent != i)
        V[i].parent = rootOf(V[i].parent);
    return V[i].parent;
}

void unify(int i, int j)
{
    int root1 = rootOf(i);
    int root2 = rootOf(j);

    if(V[root1].rank_ > V[root2].rank_)
    {
        int swap_ = root1;
        root1 = root2;
        root2 = swap_;
    }
    V[root1].parent = root2;
    if(V[root1].rank_ == V[root2].rank_)
        V[root2].rank_++;
}

struct edge{
    int v1, v2;
    int cost;
    bool chosen = false;
}E[maxM];

bool compareEdges(edge e, edge f)
{
    if(e.cost <= f.cost)
        return true;
    return false;
}

int main()
{
    fin >> N >> M;

    for(int i=1; i<=N; i++)
        V[i].parent = i;

    for(int i=1; i<=M; i++)
    {
        int X, Y, C;
        fin >> X >> Y >> C;
        E[i].v1 = X;
        E[i].v2 = Y;
        E[i].cost = C;
    }

    sort(E+1, E+1+M, compareEdges);

    int total_cost = 0;
    for(int i=1; i<=M; i++)
    {
        if(rootOf(E[i].v1) != rootOf(E[i].v2))
        {
            E[i].chosen = true;
            total_cost += E[i].cost;
            unify(E[i].v1, E[i].v2);
        }
    }

    fout << total_cost << '\n' << N-1 << '\n';
    for(int i=1; i<=M; i++)
        if(E[i].chosen)
            fout << E[i].v1 << ' ' << E[i].v2 << '\n';

	fin.close();
	fout.close();
	return 0;
}