#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int find (vector<int> &v, int i) {
	int j = i, k;
	while (v[i] != i)
		i = v[i];
	while (v[j] != j) {
		k = v[j];
		v[j] = i;
		j = k;
	}
	return i;
}


bool comp (pair < pair <int, int> , int> x, pair < pair <int, int> , int> y){
	return ((x.second - y.second) < 0);
}



void unionT (vector<int> &v, vector<int> &r, int i, int j) {
	if (r[i] < r[j])
		v[i] = j;
	else 
		if  (r[i] > r[j])
			v[j] = i;
		else {
			v[j] = i;
			r[i]++;
		}
}

void makeSet(vector<int> &parent, vector<int> &rank, int N) {
	int i;
	for (i = 0 ; i < N; i++) {
		parent.push_back(i);
		rank.push_back(1);

	}

}

long long kruskall (vector<int> &parent, vector<int> &rank,vector< pair < pair <int, int> , int> > & nodes,
	vector< pair < pair <int, int> , int> > &ama, int N, int M){
	makeSet(parent, rank, N);
	sort(nodes.begin(), nodes.end(), comp);
	long long cost = 0;
	int i = 0, x, y;
	while ( i < M ) {
		x = find(parent, nodes[i].first.first);
		y = find(parent, nodes[i].first.second);
		if (x != y) {
			cost = cost +  nodes[i].second; 
			ama.push_back(nodes[i]);
			unionT(parent, rank, x,  y);
		}
		i++;
	}
	return cost;
}

int main(int argc, char const *argv[]) {

	ifstream input_file;
	input_file.open("apm.in");
	int N, M, Q;
	input_file >> N >> M  >> Q;
	vector< pair < pair <int, int> , int> > nodes;
	vector< pair < pair <int, int> , int> > ama;
	vector<int> rank, parent;
	int i, x, y , cost, j;
	for (i = 0 ; i < M  ; i++) {
		input_file >> x >> y >> cost;
		nodes.push_back(make_pair(make_pair(x - 1, y - 1), cost));
	}

	long long cost_tot = kruskall(parent, rank, nodes, ama, N, M);
	j = ama.size();
	ofstream f("apm.out");
	f << cost_tot<<"\n";
	f << j<<"\n";
	for (i = 0; i < j; i++)
		f << ama[i].first.first<<" "<<ama[i].first.second<<"\n";


	input_file.close();
	f.close();
	return 0;
}