#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e5 + 5;
int n;
int d[N], p[N], W[N];
vector <pair<int,int>> adj[N];
vector <int> used;
void dfs(int u, int f){
used.push_back(u);
for(auto pa: adj[u]){
int v = pa.first, w = pa.second;
if(v == f) continue;
d[v] = d[u] + w;
p[v] = u, W[v] = w;
dfs(v, u);
}
}
pair<int,int> get(int u){
d[u] = 0, p[u] = -1, W[u] = 0;
used.clear();
dfs(u, -1);
int node = -1, maxi = -1;
for(int u: used){
if(d[u] > maxi){
maxi = d[u], node = u;
}
}
return {node, maxi};
}
int travelTime(int Ni, int M, int L, int A[], int B[], int T[]) {
n = Ni;
f(i,0,M){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
memset(d, -1, sizeof d);
int ans = 0;
int x = -1, y = -1, z = -1;
f(i,0,n){
if(d[i] != -1) continue;
auto ra = get(i);
auto ta = get(ra.first);
int leaf = ta.first, dim = ta.second;
int curr = 0, mini = dim;
ans = max(ans, dim);
while(leaf != ra.first){
curr += W[leaf];
mini = min(mini, max(curr, abs(dim - curr)));
leaf = p[leaf];
}
if(mini > x) z = y, y = x, x = mini;
else if(mini > y) z = y, y = mini;
else if(mini > z) z = mini;
}
ans = max(ans, x + y + L);
if(z != -1) ans = max(ans, y + z + 2*L);
return ans;
}
