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

using namespace std;

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

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()  {
    fscanf(fin, "%d%d", &n, &m);
    for(int i = 0;i < m;i++)  {
        int x, y, c;
        fscanf(fin, "%d%d%d", &x, &y, &c);
        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;
}