#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
vector <ii> adj[100010];
bool mk[100010];
int maxDist, ennd,ans;
ii p[100010];
vector <int> r;
void dfs(int v, int par, int len, int flag)
{
if(flag)
mk[v] = true;
if(len > maxDist)
{
maxDist = len;
ennd = v;
}
for(int i = 0; i < adj[v].size(); i++)
{
int u = adj[v][i].first;
if(u == par) continue;
int weight = adj[v][i].second;
if(flag)
p[u] = ii(v,weight);
dfs(u,v,len+weight,flag);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++)
{
adj[A[i]].pb(ii(B[i],T[i]));
adj[B[i]].pb(ii(A[i],T[i]));
}
for(int i = 0; i < N; i++)
{
if(mk[i]) continue;
maxDist = -1;
dfs(i,i,0,0);
maxDist = -1;
int first = ennd;
dfs(first,first,0,1);
ans = max(ans,maxDist);
int second = ennd;
int halfdiam = maxDist / 2;
int radius = 0;
for(int ver = second; ver != first; ver = p[ver].first)
{
if(radius + p[ver].second > halfdiam)
{
radius = min(radius + p[ver].second,maxDist - radius);
break;
}
radius += p[ver].second;
}
r.pb(radius);
}
sort(r.begin(),r.end());
reverse(r.begin(),r.end());
if(r.size() == 1)
return ans;
if(r.size() == 2)
return max(ans,r[0] + r[1] + L);
else
return max(ans,max(r[1] + r[2] + L + L,r[0] + r[1] + L));
}
