#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int n,m;
vector<pair<int,int> > G[100005];
int vis[100005];
int maks_dist,najoddaleceno_teme;
int ans;
map<pair<int,int>,int> edges;
void dfs(int teme,int dist,bool vis1[]){
//cout << "teme=" << teme << " dist=" << dist << endl;
bool sosedi=false;
vis[teme]=1;
vis1[teme]=1;
for (int i=0;i<G[teme].size();i++){
int next=G[teme][i].first,vreme=G[teme][i].second;
if (!vis1[next]){
sosedi=true;
vis[next]=1;
vis1[next]=1;
dfs(next,dist+vreme,vis1);
}
}
if (sosedi==false){
if (dist>maks_dist)
najoddaleceno_teme=teme,maks_dist=dist;
return;
}
}
vector<int> pat,dijametar_pat;
int d;
void dfs2(int teme,int dist,bool vis1[]){
//cout << "teme=" << teme << " dist=" << dist << endl;
bool sosedi=false;
vis[teme]=1;
vis1[teme]=1;
for (int i=0;i<G[teme].size();i++){
int next=G[teme][i].first,vreme=G[teme][i].second;
if (!vis1[next]){
sosedi=true;
vis[next]=1;
vis1[next]=1;
pat.push_back(next);
dfs2(next,dist+vreme,vis1);
pat.pop_back();
}
}
if (sosedi==false){
if (dist>=maks_dist)
maks_dist=dist,dijametar_pat=pat,ans=max(ans,dist),d=dist;
return;
}
}
vector<int> komponenta; //dist do najdalecno teme od centralnoto
void dijametar(int teme){
maks_dist=0;
najoddaleceno_teme=teme;
bool vis1[n];
memset(vis1,0,sizeof(vis1));
dfs(teme,0,vis1);
//cout << najoddaleceno_teme << endl;
memset(vis1,0,sizeof(vis1));
pat.clear();
maks_dist=0;
pat.push_back(najoddaleceno_teme);
dfs2(najoddaleceno_teme,0,vis1);
// for (int i=0;i<dijametar_pat.size();i++){
// cout << dijametar_pat[i] << " ";
// }
// cout << endl;
int centralno_teme=dijametar_pat[0];
int zbir=0;
int razlika=INT_MAX;
for (int i=1;i<dijametar_pat.size();i++){
zbir+=edges[{dijametar_pat[i-1],dijametar_pat[i]}];
int ostatok=d-zbir;
if (abs(zbir-ostatok)<razlika){
razlika=abs(zbir-ostatok);
centralno_teme=dijametar_pat[i];
}
}
//cout << "centralno_teme=" << centralno_teme << endl;
memset(vis1,0,sizeof(vis1));
maks_dist=0;
najoddaleceno_teme=centralno_teme;
dfs(centralno_teme,0,vis1);
//cout << "najoddaleceno_teme=" << najoddaleceno_teme << " maks_dist=" << maks_dist << endl;
komponenta.push_back(maks_dist);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
m=M;
for (int i=0;i<M;i++){
G[A[i]].push_back({B[i],T[i]});
G[B[i]].push_back({A[i],T[i]});
edges[{A[i],B[i]}]=T[i];
edges[{B[i],A[i]}]=T[i];
}
for (int i=0;i<N;i++){
if (vis[i]==0)
dijametar(i);
}
sort(komponenta.begin(),komponenta.end());
reverse(komponenta.begin(),komponenta.end());
if (komponenta.size()==1) return max(ans,komponenta[0]);
if (komponenta.size()==2) return max(ans,komponenta[0]+komponenta[1]+L);
ans=max(ans,komponenta[0]+komponenta[1]+L);
return max(ans,komponenta[1]+komponenta[2]+2*L);
}
