#include "dreaming.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int n = N;
    int m = M;
    int l = L;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        g[A[i]].pb({B[i], T[i]});
        g[B[i]].pb({A[i], T[i]});
    }
    vector<int> used(n, 0), h(n), sub(n);
    auto dfs = [&](int v, auto&&self) -> void {
        used[v] = 1;
        sub[v] = 0;
        for (auto &[u, w] : g[v]) {
            if (!used[u]) {
                h[u] = h[v] + w;
                self(u, self);
                sub[v] = max(sub[v], sub[u] + w);
            }
        }
    };
    int cmin = 1e9 + 1, cv = -1;
    auto dfs1 = [&](int v, int p, int up, auto&&self) -> void {
        if (max(sub[v], up) < cmin) {
            cmin = max(sub[v], up);
            cv = v;
        }
        vector<pair<int, int>> sons;
        for (auto [u, w] : g[v]) {
            if (u != p) sons.pb({sub[u] + w, u});
        }
        sort(sons.begin(), sons.end());
        for (auto [u, w] : g[v]) {
            if (u == p) continue;
            int newup = up;
            if (sons.size() > 1) {
                newup = max(newup, (sons.back().second == u ? sons[sons.size() - 2].first : sons.back().first));
            }
            self(u, v, newup + w, self);
        }
    };
    vector<pair<int, int>> lol;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, dfs);
            cmin = 1e9 + 1; cv = -1;
            dfs1(i, i, 0, dfs1);
            cout << i << ' ' << cmin << ' ' << cv << '\n';
            lol.pb({cmin, cv});
        }
    }
    sort(lol.begin(), lol.end());
    for (int i = 0; i < lol.size() - 1; i++) {
        cout << lol[i].second << ' ' << lol.back().second << '\n';
        g[lol[i].second].pb({lol.back().second, l});
        g[lol.back().second].pb({lol[i].second, l});
    }
    used.assign(n, 0);h.assign(n, 0);sub.assign(n, 0);
    int D = 0;
    auto dfs2 = [&](int v, int p, auto&&self) -> void {
        sub[v] = 0;
        vector<int> sbs;
        for (auto &[u, w] : g[v]) {
            if (u != p) {
                self(u, v, self);
                sub[v] = max(sub[v], sub[u] + w);
                sbs.pb(sub[u] + w);
            }
        }
        sort(sbs.begin(), sbs.end());
        D = max(D, sub[v]);
        if (sbs.size() >= 2) {
            D=max(D, sbs.back()+sbs[sbs.size()-2]);
        }
    };
    dfs2(0, 0, dfs2);
    return D;
}