#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define m_p make_pair
#define INF INT_MAX
#define OO LLONG_MAX
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vvpii = vector<vector<pii > >;
using u_m=unordered_map<int,int>;
template<typename T> using inverse_pq = priority_queue<T,vector<T>, greater<T> >;
template<typename T=int> void cin_vector(vector<T> &v) {for(int& i : v) cin>>i;}
pair<int,u_m> djikstra(int start, unordered_map<int, vector<pii> >& g){
inverse_pq<pii> pq;
u_m dist;
pii ans={-1,-1};
pq.push({0,start});
dist[start]=0;
while(!pq.empty()){
int w=pq.top().ff,top=pq.top().ss; pq.pop();
if(w>dist[top]) continue;
if(ans.ss<w) ans={top,w};
for(auto i :g[top]){
int d=i.ss+w;
if(dist.find(i.ff)==dist.end() or dist[i.ff]>d){
dist[i.ff]=d;
pq.push({d,i.ff});
}
}
}
return m_p(ans.ff,dist);
}
pii get_diameter_radius(unordered_map<int, vector<pii> >& g){
pair<int,u_m> pr=djikstra(g.begin()->ff,g);
int a=pr.ff;
pr=djikstra(a,g);
u_m dista=pr.ss;
u_m distb=djikstra(pr.ff,g).ss;
int radius=-1;
for(auto number : g){
// cout<<i<<": "<<dista[i]<<" "<<distb[i]<<' '<<max(dista[i],distb[i])<<endl;
int i=number.ff;
radius=radius==-1 or max(dista[i],distb[i])<radius ? max(dista[i],distb[i]) : radius;
}
return {distb[a],radius};
}
int travelTime(int N, int M, int L,
int A[], int B[], int T[]){
int n=N;
vector<vector<pii> > g(n);
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]});
}
vi p;
int maximum_diameter=0;
vector<bool> visited(n, false);
for(int i=0;i<n;i++){
if(!visited[i]){
unordered_map<int,vector<pii>> current;
visited[i]=true;
queue<int> q;
q.push(i);
current[i]={};
while(!q.empty()){
int top=q.front(); q.pop();
for(auto j : g[top]){
if(!visited[j.ff]){
q.push(j.ff);
visited[j.ff]=true;
current[j.ff].push_back({top,j.ss});
current[top].push_back({j.ff,j.ss});
}
}
}
pii pr=get_diameter_radius(current);
p.push_back(pr.ss);
maximum_diameter=max(maximum_diameter,pr.ff);
}
}
sort(p.begin(),p.end(),greater<int> ());
if(p.size()==1)
return maximum_diameter;
if(p.size()==2)
return max(maximum_diameter,p[0]+p[1]+L);
return max(maximum_diameter,max(p[0]+p[1]+L, p[1]+p[2]+2*L));
}
