#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > adjlist[100001]; //node,weight
int treenum[100001];
vector<pair<int,int> > nodesused; //node,weight
vector<int> tree;
bool visited[100001];
pair<int,int> dfs(int pos){ //furthest node,distance
if (visited[pos]) return make_pair(pos,-1e9);
tree.push_back(pos);
visited[pos]=true;
int node=pos,maxi=0;
for (auto i:adjlist[pos]){
pair<int,int> temp=dfs(i.first);
if (maxi<temp.second+i.second){
maxi=temp.second+i.second;
node=temp.first;
}
}
nodesused.push_back(make_pair(node,maxi));
//cout<<pos<<" "<<node<<" "<<maxi<<'\n';
return make_pair(node,maxi);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i=0;i<M;i++){
adjlist[A[i]].push_back(make_pair(B[i],T[i]));
adjlist[B[i]].push_back(make_pair(A[i],T[i]));
}
vector<int> radiuses;
int maxsofar=0;
for (int i=0;i<N;i++){
if (!visited[i]){
//cout<<i<<'\n';
pair<int,int> temp=dfs(i);
nodesused.clear();
for (auto nod:tree){
visited[nod]=false;
}
tree.clear();
pair<int,int> temptwo=dfs(temp.first);
tree.clear();
int mini=temptwo.second;
if (M==N-1) return mini;
maxsofar=max(maxsofar,mini);
for (auto p:nodesused){
//cout<<p.first<<" "<<p.second<<" "<<temptwo.second<<'\n';
mini=min(mini,max(p.second,temptwo.second-p.second));
}
//cout<<mini<<'\n';
radiuses.push_back(mini);
}
}
sort(radiuses.begin(),radiuses.end());
int nn=radiuses.size();
maxsofar=max(maxsofar,radiuses[nn-2]+radiuses[nn-1]+L);
if (nn>=3) maxsofar=max(maxsofar,radiuses[nn-2]+radiuses[nn-3]+L*2);
return maxsofar;
}
