#include <cstdio>
#include <vector>
#include <algorithm>
#define Mmax 400001
#define Nmax 200001
#define inf 2000000000
using namespace std;

FILE *in, *out;

int n,m,L,sum;
bool mark[200001];
vector <pair<int,int> > adj[Nmax],tree;
vector <pair<int,int> > :: iterator it;
struct heap{
    int cost,target,sauce;
}h[Mmax],nul;

void heap_pop(){
    h[1]=h[L];
    h[L]=nul;
    --L;
    int x=1,y=0;
    while(x != y){
        y = x;
        if(y*2 <= L && h[x].cost  > h[y*2].cost)x = y*2;
        if(y*2+1 <= L && h[x].cost  > h[y*2+1].cost)x = y*2+1;
        swap(h[x],h[y]);
    }
}

void heap_push(){
    int l=L;
    while(l/2 && h[l/2].cost > h[l].cost){
        swap(h[l],h[l/2]);
        l /= 2;
    }
}

int main(){
    in = fopen("apm.in","r");
    out = fopen("apm.out","w");
    int x,y,c;
    fscanf(in,"%d %d", &n, &m);
    for(register int i=0;i < m;++i){
        fscanf(in,"%d %d %d", &x, &y, &c);
        adj[x].push_back(make_pair(y,c));
        adj[y].push_back(make_pair(x,c));
    }

    mark[1]=1;
    for(it = adj[1].begin(); it != adj[1].end(); ++it){
        h[++L].cost = (*it).second;
        h[L].target = (*it).first;
        h[L].sauce = 1;
        heap_push();
    }

    while(L){
        x = h[1].target;
        y = h[1].sauce;
        c = h[1].cost;
        heap_pop();
        if(!mark[x]){
            sum += c;
            mark[x] = 1;
            tree.push_back(make_pair(y,x));
            for(it = adj[x].begin(); it != adj[x].end(); ++it){
                if(!mark[(*it).first]){
                    h[++L].cost = (*it).second;
                    h[L].target = (*it).first;
                    h[L].sauce = x;
                    heap_push();
                }
            }
        }
    }

    fprintf(out,"%d\n%d\n", sum, n-1);
    for(it = tree.begin(); it != tree.end(); ++it)fprintf(out,"%d %d\n", (*it).first, (*it).second);
    return 0;
}