#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
const int lim = 1e5 + 5;
vector<pair<int, int>>e[lim];
bitset<lim>vis;
int ans = 0, dist[3][lim], max_d, A, B;
vector<pair<int, int>>vertex;
void dfs(const int id, int s, bool upd, int& upd_vertex, int p = -1){
maximize(ans, dist[id][s]);
for(auto& [d, w] : e[s]){
if(d != p){
dist[id][d] = dist[id][s] + w;
dfs(id, d, upd, upd_vertex, s);
}
}
if(upd && maximize(max_d, dist[id][s])){
upd_vertex = s;
}
}
pair<int, int>find_root(int root){
queue<int>q;
q.push(root);
vis.set(root);
int min_d = INT_MAX, ans;
while(!q.empty()){
int u = q.front();
q.pop();
if(minimize(min_d, max(dist[1][u], dist[2][u]))){
ans = u;
}
for(auto& [v, w] : e[u]){
if(!vis.test(v)){
q.push(v);
vis.set(v);
}
}
}
return make_pair(min_d, ans);
}
void solve(int root){
max_d = -1;
dfs(0, root, true, A);
max_d = -1;
dfs(1, A, true, B);
dfs(2, B, false, A);
vertex.emplace_back(find_root(root));
}
int travelTime(int n, int m, int L, int a[], int b[], int t[]){
for(int i = 0; i < m; i++){
e[a[i]].emplace_back(b[i], t[i]);
e[b[i]].emplace_back(a[i], t[i]);
}
vis.reset();
for(int i = 0; i < n; i++){
if(!vis.test(i)){
solve(i);
}
}
sort(vertex.begin(), vertex.end());
if(vertex.size() > 1){
maximize(ans, vertex.back().first + vertex[int(vertex.size()) - 2].first + L);
}
if(vertex.size() > 2){
maximize(ans, vertex[int(vertex.size()) - 2].first + vertex[int(vertex.size()) - 3].first + (L << 1));
}
return ans;
}
