#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");


//declarare structuri

struct arc{

    int c , y;

};

struct muchie{

    int x , y , c;

};

//declarare pq

struct cmp{

    bool operator()(muchie a ,muchie b){
        return a.c > b.c;
    }

};

priority_queue< muchie , vector < muchie > , cmp > pq;

//declarare variabile

const int MAX = 2e5+1;
int n , a , b , c , m , counter;
vector < arc > v;
vector < arc > g[MAX];
bitset < MAX > in;

// prelucrare

void citire(){

    cin >> n >> m;

    while(m--){

        cin >> a >> b >> c;
        arc x;
        x.y = b;
        x.c = c;
        g[a].push_back(x);
        x.y = a;
        g[b].push_back(x);
    }

}
void prelucrare(){

    int nrn = n;
    muchie x;
    x.x = 0;
    x.y = 1;
    x.c = 0;
    pq.push(x);

    while(nrn && !pq.empty()){

        x = pq.top();
        pq.pop();
        if(in[x.y]) continue;

        arc w;
        w.c = x.x;
        w.y = x.y;
        v.push_back(w);

        nrn--;
        counter += x.c;
        int val = x.y;
        in[val] = 1;
        int l = g[val].size();

        x.x = val;

        for(int i = 0 ; i < l ; i++){

            x.y = g[val][i].y;
            x.c = g[val][i].c;
            pq.push(x);
        }

    }

}

void afisare(){

    cout << counter << '\n';

    int l = v.size();

    cout << l - 1 << '\n';

    for(int i = 1 ; i < l ; i++){
        cout << v[i].c << ' ' << v[i].y << '\n';
    }

}

int main()
{
    citire();
    prelucrare();
    afisare();

    return 0;
}