#include <fstream>
#include <algorithm>
#define st second.first
#define dr second.second
#define cost first
using namespace std;
ifstream fin ("urgenta.in");
ofstream fout ("urgenta.out");
int n, m, i, T[260], x, y, rx, ry, sol, k, S[260], D[260], u[33000], t, kk, tt, nr,q;

pair <int, pair <int, int> > L[33000];

int rad(int x){
    while(T[x]>0){
        x=T[x];
    }
    return x;
}


int main(){
    fin>>n>>m>>q;
    tt = t;
    for(i = 1; i <= n; i++)
        T[i] = -1;

    for(i = 1; i <= m ; i++){
        fin>>L[i].st>>L[i].dr>>L[i].cost;
        sol += L[i].cost;
    }

    sort(L + 1, L + m + 1);
    t = n;
    for(i = 1; i <= m; i++){
        x = L[i].st;
        y = L[i].dr;
        rx = rad(x);
        ry = rad(y);
        if(rx != ry){
            u[i]=1;
            --t;
            sol -= L[i].cost;
            if(T[rx] < T[ry]){
                T[rx] += T[ry];
                T[ry] = rx;
            }
            else{
                T[ry] += T[rx];
                T[rx] = ry;
            }
            if(t == q)
                break;
        }
    }

    fout<<sol<<"\n"<< m - (n - q)<<"\n";
    for(i=1;i<=m;i++){
        if(u[i]==0){
            fout<<L[i].st<<" "<<L[i].dr<<"\n";
        }
    }

    return 0;
}