#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define pb push_back
#define fi first 
#define se second

ifstream fin("apm.in");
ofstream fout("apm.out");

const int N = 1e5+3;

struct edge{
    int x, y, c;
    edge(){x = y = c = 0;}
    edge(int _x, int _y, int _c){x = _x; y = _y; c = _c;}
    const bool operator < (const edge &other) const {
        return c > other.c;
    }
};

int n, t, c;
bitset<N> u;
queue<pii> r;
priority_queue<edge> q;
vector<vector<pii>> e;

void read(), add(int);

int main()
{
    read();
    add(1);
    
    while (t < n){
        auto it = q.top(); q.pop();
        if (!u[it.y]){
            c += it.c; r.push({it.x, it.y});
            add(it.y);
        }
    }
    fout << c << '\n' << r.size() << '\n';
    while (!r.empty()){
        fout << r.front().fi << ' ' << r.front().se << '\n';
        r.pop();
    }

    return 0;
}

void read(){
    int m; fin >> n >> m;
    e.resize(n+2);
    while (m--){
        int a, b, c; fin >> a >> b >> c;
        e[a].pb(make_pair(b, c)); e[b].pb(make_pair(a, c));
    }
}
void add(int nod) {
    u[nod] = 1; t++;
    
    for (auto it: e[nod])
        if (!u[it.fi]) //altfel ambele noduri deja ar fi conectate
            q.push(edge(nod, it.fi, it.se));
            
}


//11:43