#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int ,int>>> adj;
vector<int> center;
vector<bool> vis;
int mx = 0;
int y = 0;
int z = 0;
void dfs1(int x , int p = -1 , int d = 0)
{
vis[x] = 1;
if(mx <= d)
{
mx = d;
y = x;
}
for(auto [u , c] : adj[x])
{
if(u == p)
continue;
dfs1(u , x , d + c);
}
}
vector<pair<int ,int>> par;
void dfs2(int x , int p = -1 , int d = 0)
{
if(mx <= d)
{
mx = d;
z = x;
}
for(auto [u , c] : adj[x])
{
if(u == p)
continue;
par[u]= {x , c};
dfs2(u , x , d + c);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
adj.assign(N , {});
vis.assign(N , 0);
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]});
}
par.assign(N , {-1 , -1});
int ans = 0;
for(int i = 0 ; i < N ; i++)
{
if(!vis[i])
{
y = 0;
mx = 0;
dfs1(i);
mx = 0;
z = 0;
dfs2(y);
int sm = 0;
int mn = mx;
ans = max(ans , mx);
int d = mx;
while(par[z].first != -1)
{
sm += par[z].second;
if(abs(mx - 2*sm) <= mn)
{
d = max(mx - sm , sm);
mn = abs(mx - 2*sm);
}
z = par[z].first;
}
center.push_back(d);
}
}
sort(center.rbegin(), center.rend());
if((int)center.size() > 1)
ans = max(ans , center[0] + center[1] + L);
if((int)center.size() > 2)
ans = max(ans , center[1] + center[2] + 2 * L);
return ans;
}
