#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5;
vector<int> node;
vector<pair<int, int>> adj[maxN];
int visited[maxN], par[maxN], Pre[maxN];
long long dis[maxN];
void dfs(int u, int pre) {
node.push_back(u);
for (auto [v, w]: adj[u]) {
if (v == pre) continue;
dis[v] = dis[u] + w;
par[v] = u; Pre[v] = w;
dfs(v, u);
}
}
long long travelTime(int N, int M, int L, vector<int> A, vector<int> B, vector<int> T) {
for (int i = 0; i < M; i++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
vector<pair<long long, int>> mid;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
node.clear();
dfs(i, i);
int u = node[0];
for (int i = 1; i < node.size(); i++)
if (dis[node[i]] > dis[u]) u = node[i];
for (auto x: node)
dis[x] = 0;
node.clear(); dfs(u, u);
int v = u;
for (auto x: node)
if (dis[x] > dis[v]) v = x;
vector<long long> pref = {0}; vector<int> path = {v};
while (v != u) {
pref.push_back(pref.back() + Pre[v]);
path.push_back(par[v]);
v = par[v];
}
long long len = pref.back(), heh = len;
int curr = v;
for (int i = 0; i < pref.size(); i++) {
int u = path[i];
if (max(len - pref[i], pref[i]) < heh) {
curr = u;
heh = max(len - pref[i], pref[i]);
}
}
mid.push_back({heh, curr});
for (auto x: node)
visited[x] = true;
}
}
sort(mid.begin(), mid.end());
for (int i = 0; i < mid.size() - 1; i++) {
int x = mid[i].second, y = mid.back().second;
adj[x].push_back({y, L});
adj[y].push_back({x, L});
}
dfs(0, 0);
int u = 0;
for (int i = 0; i < N; i++)
if (dis[i] > dis[u]) u = i;
for (int i = 0; i < N; i++)
dis[i] = 0;
dfs(u, u);
for (int i = 0; i < N; i++)
if (dis[i] > dis[u]) u = i;
return dis[u];
return 0;
}
