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

const int MAX_SIZE = 200005, MAX_VALUE = 1999999999;

int dist[MAX_SIZE]; ///the weight of the edge which connects 'i' to the MST
int pred[MAX_SIZE]; ///the predecessor of 'i' in the MST
int h[MAX_SIZE], poz[MAX_SIZE];
vector <pair <int,int>> v[MAX_SIZE], af;

void upHeap(int f){
    int key = h[f];
    while(f/2 && dist[ key ] < dist[ h[f/2] ]){
        h[f] = h[f/2];
        poz[ h[f] ] = f;
        f = f/2;
    }
    h[f] = key;
    poz[key] = f;
}

void downHeap(int l){
    int t = 1, f = 0;
    while(t != f){
        f = t;
        if(f * 2 <= l && dist[ h[f*2] ] < dist[ h[t] ])
            t = f * 2;
        if(f * 2 + 1 <= l && dist[ h[f*2+1] ] < dist[ h[t] ])
            t = f * 2 + 1;
        swap(h[f], h[t]);
        poz[ h[f] ] = f;
        poz[ h[t] ] = t;
    }
}

void insertHeap(int val, int &l){
    h[++l] = val;
    poz[val] = l;
    upHeap(l);
}

int extractTop(int &l){
    int root = h[1];
    poz[root] = 0;
    swap(h[1], h[l--]);
    poz[ h[1] ] = 1;
    downHeap(l);
    return root;
}

void updateMST(int ns){
    int sz = v[ns].size(), nbr, cost;
    for(int i=0;i<sz;i++){
        nbr = v[ns][i].first;
        cost = v[ns][i].second;
        if(dist[nbr] > cost){
            dist[nbr] = cost;
            pred[nbr] = ns;
        }
    }
}

int prim(int n){
    int l = 0, rez = 0, nbr, root, sz;

    for(int i=2;i<=n;i++)
        dist[i] = MAX_VALUE;
    updateMST(1);
    ///all the nodes are inserted, even those not affected by updateMST
    for(int i=2;i<=n;i++)
        insertHeap(i,l);

    for(int i=1;i<n;i++){
        root = extractTop(l);
        sz = v[root].size();

        ///"adds" this node (and edge) to the MST
        updateMST(root);
        rez += dist[root];
        af.push_back({pred[root], root});

        ///maintain the heap property
        for(int j=0;j<sz;j++){
            nbr = v[root][j].first;
            if(poz[nbr])
                upHeap(poz[nbr]);
        }
    }

    return rez;
}

int main()
{
    int n, m, x, y, cost;

    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>cost;
        v[x].push_back({y,cost});
        v[y].push_back({x,cost});
    }
    in.close();

    out<<prim(n)<<"\n"<<n-1<<"\n";
    for(int j=0;j<af.size();j++)
        out<<af[j].first<<" "<<af[j].second<<"\n";
    out.close();

    return 0;
}