#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector< pair<int,int> > edg[100005];
int vis[100005];
int bck[100005], dis[100005];
int mxdis = -1, mxdisnode = 0;
vector<int> v;
void dfs(int x, int p, int d) {
vis[x] = 1;
if(d>mxdis) {
mxdis = d; mxdisnode = x;
}
for(auto i:edg[x]) {
if(i.first!=p) {
bck[i.first] = x;
dis[i.first] = i.second;
dfs(i.first, x, d+i.second);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0; i<M; i++) {
edg[A[i]].push_back({B[i],T[i]});
edg[B[i]].push_back({A[i],T[i]});
}
int ans = 0;
for(int i=0; i<N; i++) {
if(vis[i]==0) {
mxdis = -1;
dfs(i, -1, 0);
mxdis = -1;
int orig = mxdisnode;
dfs(orig, -1, 0);
int ptr = mxdisnode;
int cendis = mxdis, cnt = 0;
while(ptr != orig) {
cnt += dis[ptr];
ptr = bck[ptr];
if(max(cnt, mxdis - cnt) < cendis) {
cendis = max(cnt, mxdis - cnt);
}
}
v.push_back(cendis);
}
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
ans = v[0];
if(v.size() >= 2) {
ans = max(ans, v[0] + v[1] + L);
} else {
ans = max(ans, v[0] + v[2] + L*2);
}
return ans;
}
