#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:25600000000000000000000000000000000")
#define qq cout << "!!" << endl;
#define ww cout << "??" << endl;
#define rr return 0;
#define nl cout << endl;
#define pb push_back
#define mk make_pair
#define sqr(a) a * a
#define imp(a) fixed << setprecision(a)
#define x first
#define y second
#define acmSqrt(a) __asm__ ("fsqrt" : "+t" (a));

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pp;
typedef pair<double, double> point;

int n, m, s;

int *p, *Size, minSpanTree = 0;

void makeSet(int k) {
    p[k] = k;
}

int Find(int k) {
    if(p[k] == k) {
        return k;
    }
    return p[k] = Find(p[k]);
}

vector<pp> tree;

void Union(int a, int b, int w) {
    a = Find(a);
    b = Find(b);

    if(a == b) {
        return;
    }

    minSpanTree = w;
    tree.pb(mk(a, b));

    if(Size[a] < Size[b]) {
        swap(a, b);
    }
    p[b] = a;
    Size[a] += Size[b];
}

pair<int, pp> *Q;

int main() {
    ios_base::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> n >> m >> s;

    p = new int[n + 1];
    Size = new int[n + 1];
    Q = new pair<int, pp>[m];

    for(register int i = 1; i <= n; ++i) {
        makeSet(i);
    }

    for(register int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        Q[i] = (mk(c, mk(a, b)));
    }

    sort(Q, Q + m);

    for(register int i = 0; i < m; ++i) {
        Union(Q[i].y.x, Q[i].y.y, Q[i].x);

        if(Find(1) == Find(n)) {
            break;
        }
    }

    cout << minSpanTree << " " << s << endl;

    for(auto a : tree) {
        cout << a.x << " " << a.y << endl;
    }
}