#include <iostream>
#include <set>
#include <vector>
#include <cstring>
using namespace std;

struct comparator {
    bool operator() (const pair<int,int> &a, const pair<int,int> &b) {
        if(a.second != b.second) {
            return a.second < b.second;
        }
        else {
            return a.first < b.first;
        }
    }
};

#define Nmax 200
#define BigCap 3000

int N, M;
vector<pair<int,int>> G[Nmax];
int addcost[Nmax];
int parent[Nmax];

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

    scanf("%d %d", &N, &M);
    
    for(int i = 1; i <= N; i++) {
        addcost[i] = BigCap;
    }
    addcost[1] = 0;
	
    int cost = 0;
    set<pair<int,int>,comparator> myset;
    vector<pair<int,int>> solution;

    for(int i = 1; i <= M; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        G[x].push_back(make_pair(y, z));
        G[y].push_back(make_pair(x, z));

        if(x > y) {
            swap(x, y);
        }
        if(x == 1) {
            addcost[y] = z;
            myset.insert(make_pair(y, z));
            parent[y] = 1;
        }
    }

    for(int nodes = 1; nodes <= N - 1; nodes++) {
        pair<int,int> p = *myset.begin();
        int v = p.first;
        solution.push_back(make_pair(parent[v], v));

        addcost[v] = 0;
        cost += p.second;
        myset.erase(p);

        for(auto w = G[v].begin(); w != G[v].end(); w++) {
            if(addcost[w->first] == 0) {
                continue;
            }
            if(w->second < addcost[w->first]) {
                myset.erase(make_pair(w->first, addcost[w->first]));
                myset.insert(make_pair(w->first, w->second));
                addcost[w->first] = w->second;
                parent[w->first] = v;
            }
        }
    }

    printf("%d\n", cost);
    printf("%d\n", N - 1);
    for(auto i = solution.begin(); i != solution.end(); i++) {
        printf("%d %d\n", i->first, i->second);
    }

    /*while(!myset.empty()) {
        pair<int,int> p = *myset.begin();
        myset.erase(p);
        printf("(%d,%d)\n", p.first, p.second);
    }*/

    /*myset.insert(make_pair(3,5));
    myset.insert(make_pair(3,7));
    myset.insert(make_pair(4,4));
    myset.insert(make_pair(8,6));
    myset.insert(make_pair(9,5));

    myset.erase(make_pair(4,4));
    myset.erase(make_pair(10,10));*/

    
    /*printf("%d %d\n", N, M);
	for(int i = 1; i <= N; i++) {
		printf("Node %d: ", i);
		for(auto j = G[i].begin(); j != G[i].end(); j++) {
			printf("(%d, %d)  ", (*j).first, (*j).second);
		}
		printf("\n");
	}*/
    return 0;
}