#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <ctype.h>
#include <queue>

using namespace std;

FILE *fin = fopen("apm.in", "r"), *fout = fopen("apm.out", "w");

#define BUF 1 << 17
char buf[BUF];
int pos = BUF;

inline char next()  {
    if(pos == BUF)
        fread(buf, 1, BUF, fin), pos = 0;
    return buf[pos++];
}

inline int read()  {
    int x = 0, semn = 1;
    char ch = next();
    while(!isdigit(ch) && ch != '-')
        ch = next();
    if(ch == '-')
        ch = next(), semn = -1;
    while(isdigit(ch))
        x = x * 10 + ch - '0', ch = next();
    return x * semn;
}

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

struct comparator  {
    bool operator () (elem a, elem b)  {
        return a.c > b.c;
    }
};

#define MAX_N 200000

vector <elem> v[MAX_N + 1];
vector <elem> sol;
priority_queue <elem, vector <elem>, comparator> pq;
bool inapm[MAX_N + 1];
int key[MAX_N + 1];

#define inf 2000000000

int costarb = 0, n, m;

inline void PRIM()  {
    pq.push({0, 1, 0});
    for(int i = 2;i <= n;i++)
        key[i] = inf;
    while(!pq.empty())  {
        elem e = pq.top();
        pq.pop();
        int nod = e.y;
        if(key[nod] < e.c)
            continue;
        inapm[nod] = 1;
        sol.push_back(e);
        costarb += e.c;
        for(unsigned int i = 0;i < v[nod].size();i++)  {
            int vec = v[nod][i].y, cost = v[nod][i].c;
            if(inapm[vec] || key[vec] <= cost)
                continue;
            key[vec] = cost;
            pq.push({nod, vec, cost});
        }
    }
};

int main()  {
    n = read(), m = read();
    for(int i = 0;i < m;i++)  {
        int x, y, c;
        x = read(), y = read(), c = read();
        v[x].push_back({x, y, c});
        v[y].push_back({y, x, c});
    }
    PRIM();
    fprintf(fout, "%d\n%d\n", costarb, n - 1);
    for(unsigned int i = 1;i < sol.size();i++)
        fprintf(fout, "%d %d\n", sol[i].x, sol[i].y);
    fclose(fin);
    fclose(fout);
    return 0;
}