#include <iostream>
#include <fstream>
#include <queue>
#define MAXI 20000000
using namespace std;
const int size = 1001;
ifstream fin("apm.in");
ofstream fout("apm.out");
priority_queue<int, vector<pair<int, int>>,greater<pair<int, int>>> heap;
vector<pair<int, int>> a[size];
vector<pair<int, int>> rez;
int d[size], tata[size], isInHeap[size], isInAPCM[size][size];

void init(int n) {
    for(int i = 0; i <= n; ++i) {
        d[i] = MAXI;
        tata[i] = 0;
        isInHeap[i] = 1;
    }
}

int main() {
    int i, n, m, x, y, c, sum = 0;
    fin >> n >> m;
    init(n);
    for(i = 1; i <= m; ++i) {   //liste de adiacenta
        fin >> x >> y >> c;
        a[x].push_back(make_pair(y, c));
        a[y].push_back(make_pair(x, c));
    }
    d[1] = 0;   //la primul pas, nodul 1 va fi min, pentru ca restul sunt MAX
    for(i = 1; i <= n; ++i) //construiesc heap
        heap.push(make_pair(d[i], i));
    while(!heap.empty() && heap.top().first != MAXI) {  //cat timp heap-ul nu e gol
        pair<int, int> p = heap.top(); //extrag min
        heap.pop();
        int u = p.second;
        if(u != 1 && isInAPCM[u][tata[u]] == 0){ sum += d[u]; rez.push_back(make_pair(u, tata[u]));}
        isInHeap[u] = 0;
        isInAPCM[u][tata[u]] = 1;
        for(auto v:a[u]) { //si ii parcurg vecinii
            if(isInHeap[v.first] == 1 && v.second < d[v.first]) {
                d[v.first] = v.second;
                tata[v.first] = u;
                heap.push(make_pair(d[v.first], v.first));
            }
        }
    }
    fout << sum << "\n" << rez.size() <<" \n";
    for(auto x:rez)
        fout << x.first << " " << x.second << "\n";
    return 0;
}