#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[65537], x, y, rx, ry, sol, k, S[65537], D[65537], t, kk, tt;

pair <int, pair <int, int> > L[65537];
pair <int, int> f[65537];

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


int main(){
    fin>>n>>m>>t;
    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 -= 1;
    for(i = 1; i <= m; i++){
        x = L[i].st;
        y = L[i].dr;
        rx = rad(x);
        ry = rad(y);
        if(rx != ry){
            --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 == 0)
                break;
        }
    }
    fout<<sol<<"\n";
    for(i = tt; i <= m; i++){
        f[++k].first = L[i].st;
        f[k].second = L[i].dr;
    }
    fout<<k<<"\n";
    sort(f + 1, f + k +1);
    for(i = 1; i <= k; i++)
        fout<<f[i].first<<" "<<f[i].second<<"\n";

    return 0;
}