#include<cstdio>
#include<vector>
#define MAX_N 200000
#define oo 0x3f3f3f3f
using namespace std;

vector<pair<int,int> >g[MAX_N+1], apm;
int dist[MAX_N+1], h[MAX_N+1], pos[MAX_N+1], p[MAX_N+1], n, m, minCost, heapSize;
bool used[MAX_N+1];

void readGraph() {
    int x, y, cost, i;
    FILE* fin = fopen("apm.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(i = 0; i < m; i++) {
        fscanf(fin,"%d%d%d",&x,&y,&cost);
        g[x].push_back(make_pair(y,cost));
        g[y].push_back(make_pair(x,cost));
    }
    fclose(fin);
}

inline void Swap(int i, int j) {
    int tmp = h[i];
    h[i] = h[j];
    h[j] = tmp;
    tmp = pos[h[i]];
    pos[h[i]] = pos[h[j]];
    pos[h[j]] = tmp;
}

void heapDown(int i) {
    int l, r, poz;
    l = 2 * i;
    r = 2 * i + 1;
    if(l <= heapSize && dist[h[l]] < dist[h[i]])
        poz = l;
    else poz = i;
    if(r <= heapSize && dist[h[r]] < dist[h[poz]])
        poz = r;
    if(poz != i) {
        Swap(i,poz);
        heapDown(poz);
    }
}

void heapUp(int i) {
    while(dist[h[i/2]] > dist[h[i]]) {
        Swap(i,i/2);
        i >>= 1;
    }
}

void Prim(int s) {
    vector<pair<int,int> >::iterator it;
    int i, node;
    for(i = 1; i <= n; i++) {
        dist[i] = oo;
        h[i] = pos[i] = i;
    }
    dist[s] = 0;
    Swap(1,s);
    heapSize = n;
    p[s] = 0;
    dist[0] = -oo;
    for(i = 1; i <= n; i++) {
        node = h[1];
        minCost += dist[h[1]];
        Swap(1,heapSize);
        heapSize--;
        heapDown(1);
        used[node] = true;
        if(node != s)
            apm.push_back(make_pair(node,p[node]));
        for(it = g[node].begin(); it != g[node].end(); it++) {
            if(!used[(*it).first] && dist[(*it).first] > (*it).second) {
                dist[(*it).first] = (*it).second;
                p[(*it).first] = node;
                heapUp(pos[(*it).first]);
            }
        }
    }
}

void printAPM() {
    vector<pair<int,int> >::iterator it;
    int k;
    FILE* fout = fopen("apm.out","w");
    k = apm.size();
    fprintf(fout,"%d\n%d\n",minCost,k);
    for(it = apm.begin(); it != apm.end(); it++)
        fprintf(fout,"%d %d\n",(*it).first,(*it).second);
    fclose(fout);
}

int main() {
    readGraph();
    Prim(1);
    printAPM();
    return 0;
}