#include "dreaming.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using ll = int;
using ii = pair<ll,ll>;
const ll MX = 100000;
vector<pair<ii,ll>> AL[MX]; // {{u,w},e}
bool visited[MX];
bool maxDepthMemVis[2*MX];
ll maxDepthMem[2*MX];
ii edge[MX*2]; // directional {from, to}
// returns the maximum depth
ll maxDepth(ll e)
{
if(maxDepthMemVis[e])
return maxDepthMem[e];
ll p = edge[e].first, v = edge[e].second;
ll res = 0;
for(auto& z: AL[v])
{
ll u = z.first.first;
ll w = z.first.second;
ll ne = z.second;
if(u==p) continue;
res = max(res, maxDepth(ne)+w);
}
maxDepthMemVis[e] = 1;
maxDepthMem[e] = res;
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(ll i=0;i<M;i++)
{
ll a = A[i], b=B[i], w=T[i];
AL[a].push_back({{b,w},2*i});
AL[b].push_back({{a,w},2*i+1});
edge[2*i] = {a,b};
edge[2*i+1] = {b,a};
}
vector<ll> ecc; // eccentricity vector
ll res = 0;
for(ll i=0;i<N;i++)
{
if(visited[i]) continue;
vector<ll> nodes;
queue<ll> q;
q.push(i);
visited[i]=1;
nodes.push_back(i);
while(!q.empty())
{
ll v = q.front(); q.pop();
for(auto& z: AL[v])
{
ll u = z.first.first;
if(visited[u]) continue;
q.push(u);
visited[u]=1;
nodes.push_back(u);
}
}
//cout<<"nodes: "; for(ll v: nodes) cout<<v<<" "; cout<<"\n";
ll mnMxDepth = 1e10;
for(ll v: nodes)
{
ll mxDepth = 0;
for(auto& z: AL[v])
{
ll u = z.first.first;
ll w = z.first.second;
ll ne = z.second;
mxDepth=max(mxDepth, maxDepth(ne)+w);
}
res = max(res,mxDepth);
mnMxDepth = min(mnMxDepth, mxDepth);
}
ecc.push_back(mnMxDepth);
}
sort(ecc.begin(),ecc.end(),greater<ll>());
//cout<<"ecc: "; for(ll x: ecc) cout<<x<<" "; cout<<"\n";
res = max(res, ecc[0]);
if(ecc.size()>=2) res=max(res,ecc[0]+ecc[1]+L);
if(ecc.size()>=3) res=max(res,ecc[1]+ecc[2]+2*L);
return res;
}
