#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100100
int dist[MAXN];
int visited[MAXN];
int far;
int pai[MAXN];
vector<pair<int, int>> adj[MAXN];
void dfs(int v, int p) {
visited[v]=1;
pai[v]=p;
if(dist[v]>dist[far]) far=v;
for(auto e : adj[v]) {
if(e.first==p) continue;
dist[e.first]=dist[v]+e.second;
dfs(e.first, v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(visited, 0, sizeof(visited));
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]});
}
vector<int> trees;
for(int i=0;i<N;i++) {
if(visited[i]) continue;
dist[i]=0;
far=i;
dfs(i, -1);
dist[far]=0;
dfs(far, -1);
int v=far;
int bst=1e9;
while(v!=-1) {
bst=min(bst, max(dist[v], dist[far]-dist[v]));
v=pai[v];
}
trees.push_back(bst);
}
sort(trees.rbegin(), trees.rend());
deque<int> dq;
for(int i=0;i<trees.size();i++) {
int t=trees[i];
if(i%2==0) dq.push_back(t);
else dq.push_front(t);
}
int ans=0;
int curFar=0;
for(auto t : dq) {
ans=max(ans, t+curFar);
curFar=max(curFar, t)+L;
}
return ans;
}
