#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >adjlist[100000];
bool visited[100000];
pair<int,int> maxi={0,INT_MAX};
void dfs(int node,int dist_so_far){
if(visited[node]==false){
visited[node]=true;
if(maxi.first<dist_so_far || (maxi.first==dist_so_far && maxi.second>node)){
maxi={dist_so_far,node};
}
for(int i=0;i<adjlist[node].size();i++){
if(visited[adjlist[node][i].first]==false){
dfs(adjlist[node][i].first,adjlist[node][i].second+dist_so_far);
}
}
}
}
vector<int>yes;
stack<int>hmph;
void dfs2(int node,int dist_so_far){
if(visited[node]==false){
visited[node]=true;
hmph.push(node);
if(maxi.first==dist_so_far && maxi.second==node){
while(hmph.size()){
yes.push_back(hmph.top());
hmph.pop();
}
reverse(yes.begin(),yes.end());
}
for(int i=0;i<adjlist[node].size();i++){
if(visited[adjlist[node][i].first]==false){
dfs(adjlist[node][i].first,adjlist[node][i].second+dist_so_far);
}
}
hmph.pop();
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
map<pair<int,int>,int>mp;
for(int i=0;i<M;i++){
adjlist[A[i]].push_back({B[i],T[i]});
adjlist[B[i]].push_back({A[i],T[i]});
mp[{A[i],B[i]}]=T[i];
mp[{B[i],A[i]}]=T[i];
}
for(int i=0;i<N;i++) visited[i]=false;
vector<int>starting;
for(int i=0;i<N;i++){
if(visited[i]==false){
dfs(i,0);
starting.push_back(maxi.second);
maxi={0,INT_MAX};
}
}
for(int i=0;i<N;i++){
visited[i]=false;
}
vector<pair<int,int> > diameters;
vector<vector<int> > paths;
vector<pair<int,int> > maxrecord;
for(int i=0;i<starting.size();i++){
dfs(starting[i],0);
diameters.push_back({starting[i],maxi.second});
maxrecord.push_back(maxi);
maxi={0,INT_MAX};
}
for(int i=0;i<N;i++){
visited[i]=false;
}
for(int i=0;i<starting.size();i++){
maxi=maxrecord[i];
dfs2(starting[i],0);
paths.push_back(yes);
yes.clear();
}
int ans=0;
vector<int>segments;
for(int i=0;i<paths.size();i++){
ans=max(ans,maxrecord[i].first);
int good=INT_MAX;
int sofar=0;
for(int j=0;j<paths[i].size();j++){
if(max(maxrecord[i].first-sofar,sofar)<good){
good=max(maxrecord[i].first-sofar,sofar);
sofar+=mp[{paths[i][j],paths[i][j+1]}];
}
else break;
}
segments.push_back(good);
}
int d=segments.size();
sort(segments.begin(),segments.end());
ans=max(ans,segments[d-1]+segments[d-2]+L);
ans=max(ans,segments[d-2]+segments[d-3]+2*L);
return ans;
}
