#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using pii = pair<int, int>;
const int INF = 1e9+7;
vector<vector<pii>> adj;
vector<pii> centrs;
vector<bool> seen;
vector<int> sfm;
pii ca={INF, -1};
int res =0;
int dfs1(int node, int p=-1){
seen[node]=true;
for(auto [n2, w]:adj[node]){
if(n2==p)continue;
int x = dfs1(n2, node);
sfm[node]=max(sfm[node], w+x);
}
return sfm[node];
}
void dfs2(int node, int p=-1, int bu=0){
vector<vector<int>> nes;
for(auto [n2, w]:adj[node]){
if(n2!=p)nes.push_back({w+sfm[n2], n2, w});
}
if(adj[node].empty()){
ca={0, node};
return;
}
else if(nes.empty()){
return;
}
sort(all(nes));
reverse(all(nes));
if(max(bu, nes[0][0])<ca.first){
ca={max(bu, nes[0][0]), node};
}
int mbu=bu;
for(int i = 1;i<nes.size();i++)mbu=max(mbu, nes[i][0]);
dfs2(nes[0][1], node, mbu+nes[0][2]);
}
pii flp(int node, int p=-1){
pii resn={node, 0};
for(auto thing:adj[node]){
if(thing.first==p)continue;
auto x=flp(thing.first, node);
if(x.second+thing.second>resn.second){
resn={x.first, x.second+thing.second};
}
}
return resn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N+1);
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]});
}
seen.assign(N+1, false);
sfm.assign(N+1, 0);
for(int i = 0;i<N;i++){
if(!seen[i]){
dfs1(i);
ca={INF, -1};
dfs2(i);
centrs.push_back(ca);
auto tt=flp(i);
res=max(res, flp(tt.first).second);
}
}
sort(all(centrs));
reverse(all(centrs));
if(centrs.size()==1){
res=max(res, centrs[0].first);
}
else if(centrs.size()==2){
res=max(res, centrs[0].first+centrs[1].first+L);
}
else{
res=max(res, max(centrs[0].first+centrs[1].first+L, centrs[1].first+centrs[2].first+2*L));
}
return res;
}
