# include <fstream>
# include <algorithm>
# include <vector>
# define fi first.first
# define sec first.second
# define cost second

using namespace std;

ifstream f ( "urgenta.in" );
ofstream g ( "urgenta.out" );

int n, m, k, total, s, sum;
bool ok = 1;
vector < pair < pair < int, int >, int > > v;
vector < pair < pair < int, int >, int > > :: iterator itt;
vector < pair < int, int > > answer;
vector < pair < int, int > > muchii;
vector < pair < int, int > > :: iterator it;
vector < int > c;

int compare( pair < pair < int, int >, int > P1, pair < pair < int, int >, int > P2 ) { // compare pentru sort
    if ( P1.second < P2.second )
        return 1;
    return 0;
}

int componenta( int x ) {
    while ( c[x] != x )
        x = c[x];
    return x;
}

void Read() {

    f >> n >> m >> k;
    for ( int i = 0; i < m; ++ i ) {
        int x, y, c;
        f >> x >> y >> c;
        v.push_back( make_pair( make_pair( x, y ), c ) );
        sum = sum + c;
    }
    if ( n == k )
    {
        ok = 0;
        g << sum << '\n';
        g << m << '\n';
        for ( itt = v.begin(); itt != v.end(); ++ itt ) {
            g << itt -> first.first << " " << itt -> first.second << '\n';
        }
    }
}

void Kruskal() {

    sort( v.begin(), v.end(), compare );

    c.resize( n + 1 );
    for ( int i = 1; i <= n; ++ i ) {
        c[i] = i;
    }
    int in = 0;
    int edges = 0;
    for ( int i = 0; i < m && edges < n - k; ++ i ) {
        int a = componenta( v[i].fi );
        int b = componenta( v[i].sec );
        if ( a != b ) {
            ++ edges;
            total = total + v[i].cost;
            //answer.push_back( make_pair( v[i].fi, v[i].sec ) );
            if ( a > b ) c[b] = a;
            else c[a] = b;
        }
        else {
            muchii.push_back( make_pair( v[i].fi, v[i].sec ) );
            s = s + v[i].cost;
        }
        in = i;
    }

    for ( int j = in + 1; j < m; ++ j ) {
        muchii.push_back(  make_pair( v[j].fi, v[j].sec ) );
        s = s + v[j].cost;
    }

}

void Afisare() {

    g << s << '\n';
    g << muchii.size() << '\n';
    for ( it = muchii.begin(); it != muchii.end(); ++ it ) {
        g << it -> first << " " << it -> second << '\n';
    }
}

void Solve() {

    Read();
    Kruskal();
    if ( ok )
        Afisare();
}

int main()
{
    Solve();

    return 0;
}