#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;
static int mx, cn;
static bool viz[nmax + 1];
static pair<int, int> tata[nmax + 1];
static vector<pair<int, int>> g[nmax + 1];
void dfs (int nod, int t, int h) {
viz[nod] = 1;
if (h > mx) {
mx = h;
cn = nod;
}
for (auto i : g[nod]) {
if (i.first != t) {
dfs(i.first, nod, h + i.second);
tata[i.first] = {nod, i.second};
}
}
}
int cauta (int nod) {
mx = -1;
cn = -1;
dfs(nod, -1, 0);
return cn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; ++ i) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<int> dst;
int lmax = 0;
for (int i = 0; i < N; ++ i) {
if (viz[i] == 0) {
int c1 = cauta(i);
cauta(c1);
int x = cn, aux = mx, lst = 0;
while (aux > mx / 2) {
aux -= tata[x].second;
lst = tata[x].second;
x = tata[x].first;
}
dst.push_back(min(mx - aux, aux + lst));
// cout << dst.back() << "\n";
lmax = max(lmax, mx);
}
}
sort(dst.begin(), dst.end());
reverse(dst.begin(), dst.end());
int leg = 0;
if (dst.size() >= 2)
leg = max(leg, dst[0] + L + dst[1]);
if (dst.size() >= 3)
leg = max(leg,dst[1] + dst[2] + 2 * L);
return max(lmax, leg);
}
