#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<int(b); i++)
vector<vector<pair<int,int> > > G(100000);
bool flags[3][100000];
int largestdist;
int farthestnode;
vector<int> diameter;
//call from one node, farthestnode would then be node farthest away
void dfs(int node,int currdist,int iter) {
if (flags[iter][node]) return;
if (currdist>largestdist) {
largestdist=currdist;
farthestnode=node;
}
flags[iter][node]=true;
for (auto x:G[node]) {
int other=x.first;
int cost=x.second;
dfs(other,currdist+cost,iter);
}
}
bool dfs2(int node, int dest) {
if (node==dest) {return true;}
if (flags[2][node]) return false;
flags[2][node]=true;
for (auto x:G[node]) {
if (dfs2(x.first,dest)) {diameter.push_back(x.second); return true;}
}
return false;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
//For each connected component, find radius and diameter
vector<int> diameters;
vector<int> radiuses;
rep(i,0,M) {
int a,b;
a=A[i];
b=B[i];
int c=T[i];
G[a].push_back(make_pair(b,c));
G[b].push_back(make_pair(a,c));
}
rep (i,0,N) {
if (flags[0][i]) continue;
//New subgraph
largestdist=-1;
farthestnode=-1;
dfs(i,0,0);
int a,b;
a=farthestnode;
largestdist=-1;
farthestnode=-1;
dfs(a,0,1);
b=farthestnode;
diameter.clear();
dfs2(a,b);
diameters.push_back(largestdist);
//Now just find centroid
int count=0;
int radius=largestdist;
for (auto x:diameter) {
count+=x;
radius=min(radius,max(count,largestdist-count));
}
assert(count==largestdist);
radiuses.push_back(radius);
}
int ans=diameters[0];
for (auto x:diameters) {
ans=max(ans,x);
}
sort(radiuses.begin(),radiuses.end());
int numradius=radiuses.size();
if (numradius>=2) {
ans=max(ans,radiuses[numradius-1]+radiuses[numradius-2]+L);
}
if (numradius>=3) {
ans=max(ans,radiuses[numradius-2]+radiuses[numradius-3]+2*L);
}
return ans;
}
