#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxN = 1e5;
vector<vector<pair<int,int>>> graph(maxN);
vector<int> dis1, dis2, dis0;
vector<bool> vis;
string wa;
pair<int,int> dfs(int node, int par, vector<int>&dis){
pair<int,int> lejos = {node, dis[node]};
pair<int,int> comp;
for(auto u : graph[node]){
if(dis[u.first] == -1){
dis[u.first]=dis[node]+u.second;
comp = dfs(u.first, node, dis);
if(comp.second > lejos.second) lejos = comp;
}
}
return lejos;
}
int find_mid(int node, int&sz){
int ans = 1e9+83;
vis[node] = true;
if(dis1[node]+dis2[node]==sz) ans = min(ans, max(dis1[node], dis2[node]));
for(auto u : graph[node]) if(!vis[u.first]) ans = min(ans, find_mid(u.first, sz));
//if(ans == 1e9+83) return 0;
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
// Fixing whatever this "input" is supposed to be
for(int i = 0; i < M; ++i){
graph[A[i]].push_back({B[i], T[i]});
graph[B[i]].push_back({A[i], T[i]});
}
pair<int,int> p;
int ans;
dis0 = dis1 = dis2 = vector<int>(N, -1);
vis = vector<bool>(N, false);
vector<int> r;
for(int i = 0; i < N; ++i){
if(dis0[i] == -1){
dis0[i] = 0;
p = dfs(i,i, dis0);
dis1[p.first] = 0;
p = dfs(p.first, p.first, dis1);
dis2[p.first] = 0;
p = dfs(p.first, p.first, dis2);
vis[p.first] = true;
ans = find_mid(p.first, p.second);
r.push_back(ans);
}
}
sort(r.begin(), r.end()); reverse(r.begin(), r.end());
ans = 0;
if(r.size() >= 2) ans = max(ans, r[0]+r[1]+L);
if(r.size() >= 3) ans = max(ans, r[1]+r[2]+2*L);
return ans;
}
