#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
// cout << "input : " << N << " " << M << " " << L << endl;
// for(int i = 0;i<M;i++){
// cout << "edge : " << A[i] << " " << B[i] << " " << T[i] << endl;
// }
vector < pair < int , int > > tree[N];
int vis[N] = {0};
for(int i = 0;i<M;i++){
tree[A[i]].push_back({B[i] , T[i]});
tree[B[i]].push_back({A[i] , T[i]});
}
// cout << "done1" << endl;
vector < int > vec;
int maxi = 0;
for(int i = 0;i<N;i++){
if(vis[i] == 0){
// cout << "starting at : " << i << endl;
auto furthest = [&](int st){
map < int , int > visited;
priority_queue < pair < int , int > > pq;
pq.push({0,st});
pair < int , int > ret = {0,st};
while(!pq.empty()){
auto tmp = pq.top();
pq.pop();
if(visited[tmp.second])continue;
vis[tmp.second] = 1;
// cout << "visited : " << tmp.first << " " << tmp.second << endl;
visited[tmp.second] = 1;
ret = max(ret , {-tmp.first , tmp.second});
for(auto itr : tree[tmp.second]){
// cout << "pushing : " << tmp.first - itr.second << " , " << itr.first << endl;
pq.push({tmp.first - itr.second , itr.first});
}
}
return ret.second;
};
int node1 = furthest(i);
// cout << "NODE1 : " << node1 << endl;
int node2 = furthest(node1);
// cout << "NODE2 : " << node2 << endl;
// cout << "done3" << endl;
vector < int > path;
function<bool(int,int,int)> dfs = [&](int node , int par , int parcost){
// cout << "dfs : " << node << " " << par << " " << parcost << endl;
if(node == node2){
path.push_back(parcost);
return true;
}
bool bl = 0;
for(auto itr : tree[node]){
if(itr.first == par)continue;
// cout << node << " -> " << itr.first << endl;
if(dfs(itr.first,node,itr.second)){
path.push_back(parcost);
bl = 1;
}
}
return bl;
};
dfs(node1,node1,0);
// cout << "path : ";for(auto itr : path)cout << itr << " ";cout << endl;
// cout << "done4" << endl;
int sum = accumulate(all(path) , 0ll) , cursum = 0 , locans = sum;
maxi = max(maxi , sum);
for(int i = 0;i<sz(path);i++){
cursum += path[i];
locans = min(locans , max(cursum , sum-cursum));
}
// cout << "locans : " << locans << endl;
vec.push_back(locans);
}
}
sort(all(vec) , greater < int >{});
if(sz(vec) == 1)return max(maxi , vec[0]);
else if(sz(vec) == 2)return max(maxi , vec[0] + vec[1] + L);
else return max({maxi , vec[0] + vec[1] + L , vec[1] + vec[2] + 2 * L});
}
