#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

FILE *fin, *fout;

int n, m;

struct edge
{
    int start, dest, cost;
};

const int NMAX = 200000;
edge v[NMAX + 5];
int father[NMAX + 5] , depth[NMAX + 5];
vector <edge> rez;

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

int get_root(int node)
{
    if(node == father[node])
        return node;

    return father[node] = get_root(father[node]);
}

void union_m(int node1, int node2)
{
    int r1 = get_root(node1), r2 = get_root(node2);

    father[r1] = r2;
}

int s;

int main()
{
    fin = fopen("apm.in", "r");
    fout = fopen("apm.out", "w");

    fscanf(fin, "%d%d", &n, &m);

    for(int i = 1; i <= m; i++)
    {
        fscanf(fin, "%d%d%d", &v[i].start, &v[i].dest, &v[i].cost);
    }

    sort(v + 1, v + m + 1, cmp);

    for(int i = 1; i <= n; i++)
        father[i] = i;

    for(int i = 1; i <= m; i++)
    {
        if(get_root(v[i].dest) != get_root(v[i].start))
           {
               s += v[i].cost;

               union_m(v[i].start , v[i].dest);
               rez.push_back(v[i]);
           }
    }

    fprintf(fout , "%d\n" , s);
    fprintf(fout , "%d\n" , n - 1);

    for(auto it : rez)
        fprintf(fout , "%d %d\n" , it.start , it.dest);

    fclose(fin);
    fclose(fout);
    return 0;
}