#include "dreaming.h"
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
const ll INF = 1e18;
int N, M, L;
vector<int> h, to, nx, w, vis, par;
vector<ll> d;
ll get(int s, ll r){
vector<int> ord;
stack<int> st;
vis[s] = 1, par[s] = -1, st.push(s), ord.pb(s);
while(st.size()){
int u = st.top();
st.pop();
for(int i = h[u]; i != -1; i = nx[i]){
int v = to[i];
if(v == par[u] or vis[v]) continue;
vis[v] = 1, par[v] = u, d[v] = d[u] + w[i];
st.push(v), ord.pb(v);
}
}
int a = s;
for(auto u:ord){
if(d[u] > d[a]) a = u;
}
st.push(a);
par[a] = -1;
d[a] = 0;
while(st.size()){
int u = st.top();
st.pop();
for(int i = h[u]; i != -1; i = nx[i]){
int v = to[i];
if(v == par[u]) continue;
par[v] = u, d[v] = d[u] + w[i];
st.push(v);
}
}
int b = a;
for(auto u:ord){
if(d[u] > d[b]) b = u;
}
ll D = d[b];
r = INF;
for(int x = b; x != -1; x = par[x]) r = min(r, max(d[x], D - d[x]));
return D;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
N = n, M = m, L = l;
h.assign(N, -1), to.assign(2 * M, 0), nx.assign(2 * M, 0), w.assign(2 * M, 0);
vis.assign(N, 0), par.assign(N, -1), d.assign(N, 0);
int ec = 0;
for(int i = 0; i < M; i++){
to[ec] = B[i];
w[ec] = T[i];
nx[ec] = h[A[i]];
h[A[i]] = ec;
ec++;
to[ec] = A[i];
w[ec] = T[i];
nx[ec] = h[B[i]];
h[B[i]] = ec;
ec++;
}
vector<ll> rad;
ll mx = 0;
for(int i = 0; i < N; i++){
if(vis[i]) continue;
ll r, D = get(i, r);
mx = max(mx, D);
rad.pb(r);
}
sort(rad.begin(), rad.end());
reverse(rad.begin(), rad.end());
if(rad.size() >= 2) mx = max(mx, rad[0] + rad[1] + L);
if(rad.size() >= 3) mx = max(mx, rad[1] + rad[2] + 2 * L);
return (int)mx;
}
