#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];
bool viz[LIM];
int dist[LIM];
int with[LIM];

void calc() {
    dist[1] = 0;
    with[1] = 0;
    bool first = true;
    int totalC = 0;
    for(int c = 1; c <= n; c++) {
        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;
            }
        }
        totalC += dist[pos];
        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) {
                    dist[vec] = cost;
                    with[vec] = pos;
                }
            }
        }
    }

    cout << totalC << "\n";
    cout << n - 1 << "\n";
    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)
                cout << i << " " << res[i][j] << "\n";
        }
    }

}

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;
}