#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)(1e5)+5;
vector<pair<int, int>> adj[MAXN];
int cur = -1;
int curI = -1;
pair<int, int> best;
bool visited[MAXN];
vector<pair<int, int>> total;
void furthest(int n, int p, int d) {
visited[n] = true;
if (d > cur) {
cur = d;
curI = n;
}
for (pair<int, int> e : adj[n]) {
if (e.first != p) {
furthest(e.first, n, d+e.second);
}
}
}
int getBest(int n, int p, int d) {
int distTo = (n == curI ? 0 : (int)(1e9)) ;
for (pair<int, int> e : adj[n]) {
if (e.first != p) {
distTo = min(distTo, getBest(e.first, n, d+e.second) + e.second);
}
}
if (max(d, distTo) < best.first) {
best = {max(d, distTo), min(d, distTo)};
}
return distTo;
}
void getSplit(int n) {
cur = -1;
furthest(n, n, 0);
cur = -1;
int d1 = curI;
furthest(d1, d1, 0);
best = {(int)(1e9), (int)(1e9)};
getBest(d1, d1, 0);
total.push_back(best);
}
int travelTime(int N, int M, int L, int A[], int B[], 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]});
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
getSplit(i);
}
}
sort(total.rbegin(), total.rend());
pair<int, int> cur = total[0];
for (int i = 1; i < total.size(); i++) {
if (total[i].first + L > cur.second) {
cur = {max(total[i].first + L, cur.first), min(total[i].first+L, cur.first)};
}
}
return cur.first + cur.second;
}
