#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <string>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define LIM 200005
#define INF 10000

int n, m;
vector<pair<int, int> > v[LIM];
vector<int> res[LIM];
set<pair<int, int> > s;
bool viz[LIM];
int dist[LIM];
int with[LIM];

void calc() {
    dist[1] = 0;
    with[1] = 0;
    s.insert(make_pair(0, 1));
    int totalC = 0;
    for(int c = 1; c <= n; c++) {
        // asta e pentru n^2
//        int pos = -1, mn = INF;
//        for(int i = 1; i <= n; i++) { // aleg pe cel care e cel mai apropiat de graf (are la dist minim)
//            //dist = cost minim catre toate nodurile deja introduse
//            if(mn > dist[i] && !viz[i]) {
//                mn = dist[i];
//                pos = i;
//            }
//        }

        // acum caut in mlogn minimul
        int pos, cost;
        pair<int, int> f = (*s.begin());
        pos = f.second;
        cost = f.first;
        while(viz[pos] == true && s.size() > 0) {
            s.erase(s.begin());
            f = (*s.begin());
            pos = f.second;
            cost = f.first;
        }

        totalC += cost;
        res[pos].push_back(with[pos]);

        dist[pos] = 0;
        viz[pos] = true;
        for(int i = 0; i < (int) v[pos].size(); i++) {
            int vec = v[pos][i].first;
            if(!viz[vec]) {
                int cost = v[pos][i].second;
                if(dist[vec] > cost && dist[vec] != 0) {
                    s.insert(make_pair(cost, vec));
                    dist[vec] = cost;
                    with[vec] = pos;
                }
            }
        }
    }

    printf("%d\n", totalC);
    printf("%d\n", n - 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < (int) res[i].size(); j++) {
            if(res[i][j] >= 1 && res[i][j] <= n)
                printf("%d %d\n", i, res[i][j]);
        }
    }

}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out","w", stdout);

    int x, y, c;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &c);
        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }

    // constructie arbore;
    fill(dist, dist + n + 1, INF);
    calc();

	return 0;
}