#include <fstream>
#include <map>
#include <vector>

using namespace std;

const int MAXN = 200005, MAXM = 400005;

struct triple{
    int el1, el2, el3;
}edge[MAXM];

#define fr first
#define sec second

int n, m, heapsz;
pair<int, int> pq[MAXN];
map<int, int> pos, ans;
vector<triple> graf[MAXN];

void heap_sus(int p){
    while(p > 1){
        if(pq[p].fr < pq[p / 2].fr){
            swap(pos[pq[p].sec], pos[pq[p / 2].sec]);
            swap(pq[p], pq[p / 2]);
            p /= 2;
        }
        else break;
    }
}

void heap_jos(int p){
    while(p <= heapsz){
        int f1 = 2 * p, f2 = 2 * p + 1, np = p;
        if(f1 <= heapsz && pq[p].fr > pq[f1].fr) np = f1;
        if(f2 <= heapsz && pq[np].fr > pq[f2].fr) np = f2;
        if(np != p){
            swap(pos[pq[p].sec], pos[pq[np].sec]);
            swap(pq[p], pq[np]);
            p = np;
        }
        else break;
    }
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> edge[i].el1 >> edge[i].el2 >> edge[i].el3;
        graf[edge[i].el1].push_back({edge[i].el2, edge[i].el3, i});
        graf[edge[i].el2].push_back({edge[i].el1, edge[i].el3, i});
    }
    pq[++heapsz] = make_pair(0, 1);
    pos[1] = heapsz;
    for(int i = 2; i <= n; ++i){
        pq[++heapsz] = make_pair(1e9, i);
        pos[i] = heapsz;
    }
    int sum = 0;
    while(heapsz){
        int top = pq[1].sec;
        sum += pq[1].fr;
        pos[pq[heapsz].sec] = 1;
        swap(pq[1], pq[heapsz]);
        pos[pq[heapsz].sec] = 0;
        heapsz--;
        heap_jos(1);
        for(auto x : graf[top]){
            if(pos[x.el1] == 0) continue;
            if(pq[pos[x.el1]].fr > x.el2){
                pq[pos[x.el1]].fr = x.el2;
                ans[x.el1] = x.el3;
                heap_sus(pos[x.el1]);
            }
        }
    }
    fout << sum << "\n" << ans.size() << "\n";
    for(int i = 2; i <= n; ++i)
        fout << edge[ans[i]].el1 << " " << edge[ans[i]].el2 << "\n";
    return 0;
}