#include <bits/stdc++.h>

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){
    for(int i = p; i >= 2; i /= 2){
        if(pq[i].fr < pq[i / 2].fr){
            swap(pos[pq[i].sec], pos[pq[i / 2].sec]);
            swap(pq[i], pq[i / 2]);
        }
        else break;
    }
}

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

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    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;
    }
    while(heapsz){
        int top = pq[1].sec;
        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]);
            }
        }
    }
    int sum = 0;
    for(int i = 2; i <= n; ++i)
        sum += edge[ans[i]].el3;
    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;
}