#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");

struct edge {
    int x, y, c;
};

const int NMAX = 400005;
const int MMAX = 500005;
vector < edge > edges(MMAX);
int N, M, sum, tata[NMAX], rang[NMAX];
edge mst[NMAX - 1];

void citire()
{
    fin >> N >> M;
    int x, y, c;
    for (int i = 0; i < M; i++)
    {
        fin >> x >> y >> c;
        edge e;
        e.x = x; e.y = y; e.c = c;
        edges.push_back(e);
    }
}

bool cmp(edge e1, edge e2)
{
    return e1.c < e2.c;
}

int find(int nod)
{
    while(tata[nod] != nod)
        nod = tata[nod];
    return nod;
}

void uniune(int x, int y)
{
    int tata_x = find(x);
    int tata_y = find(y);
    
    if(rang[tata_x] < rang[tata_y])
    {
        tata[tata_x] = tata_y;
        rang[tata_y]++;
    }
    else
    {
        tata[tata_y] = tata_x;
        rang[tata_x]++;
    }
}

void kruskal()
{
    sort(edges.begin(), edges.end(), cmp);
    for(int i = 1; i <= N; i++)
        tata[i] = i;
    int count = 0, i = 0;
    while(count != N - 1)
    {
        edge curr_edge = edges[i];
        if(find(curr_edge.x) != find(curr_edge.y))
        {
            uniune(curr_edge.x, curr_edge.y);
            sum += curr_edge.c;
            mst[count++] = curr_edge;
        }
        i++;
    }
}

void print()
{
    fout << sum << '\n' << N - 1 << '\n';
    for(int i = 0; i < N - 1; i++)
        fout << mst[i].x << ' ' << mst[i].y << '\n';
}

int main()
{
    citire();
    kruskal();
    print();
    return 0;
}