#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <queue>
#include <set>
#include <stack>

using namespace std;

int n, m, k;
const int NMAX = 100001;

int capacitate[NMAX];

struct Edge {
	int u, v, w;

	Edge() = default;

	Edge(int u, int v, int w) : u(u), v(v), w(w) {}

	friend bool operator<(const Edge& lhs, const Edge& rhs) {
		return lhs.w < rhs.w;
	}
};

struct DSU {
	int parinte[NMAX];
	DSU(int n) {
		for(int i = 0; i < n; i++) parinte[i] = i;
	}

	int find(int i) {
		if(parinte[i] == i) return i;
		return parinte[i] = find(parinte[i]);
	}

	void unite(int i, int j) {
		int rooti = find(i);
		int rootj = find(j);

		if(rooti != rootj) {
			parinte[rooti] = rootj;
		}
	}
};

int main() {
	cin >> n >> m >> k;
	vector<Edge> muchii(m);
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		muchii[i].u = u;
		muchii[i].v = v;
		muchii[i].w = w;
	}

	sort(muchii.begin(), muchii.end());
	DSU dsu(n + 1);

	priority_queue<Edge> apm;
	for(int i = 0; i < m; i++) {
		auto [u, v, w] = muchii[i];
		if(dsu.find(u) == dsu.find(v)) continue;

		dsu.unite(u, v);
		apm.emplace(u, v, w);
	}

	for(int i = 0; i < k - 1; i++) {
		apm.pop();
	}

	set<pair<int, int>> muchiiRamase;

	while(!apm.empty()) {
		auto [u, v, w] = apm.top();
		apm.pop();

		muchiiRamase.emplace(u, v);
	}

	int gravitatie = 0;
	int nrIntrerupte = 0;
	vector<Edge> muchiiRezultat;
	for(int i = 0; i < m; i++) {
		auto [u, v, w] = muchii[i];
		if(muchiiRamase.find(pair(u, v)) != muchiiRamase.end()) continue;

		gravitatie += w;
		nrIntrerupte++;
		muchiiRezultat.emplace_back(u, v, w);
	}
	cout << gravitatie << endl << nrIntrerupte << endl;
	for(auto [u, v, w] : muchiiRezultat) cout << u << " " << v << endl;

	return 0;
}