#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int INF = 1e9+5;
vector<pair<int, int>> g[maxn];
int d1[maxn], d2[maxn], vis[maxn];
vector<int> vec;
void pre_dfs(int x, int p){
vis[x] = 1;
vec.push_back(x);
for(auto v: g[x]){
if(v.first == p)continue;
pre_dfs(v.first, x);
}
}
void dfs(int x, int p, int* D){
if(p == -1)D[x] = 0;
for(auto v: g[x]){
if(v.first == p)continue;
D[v.first] = D[x] + v.second;
dfs(v.first, x, D);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int ans = 0;
vector<int> hdm;
for(int i = 0; i < M; i++){
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
for(int i = 0; i < N; i++){
if(vis[i])continue;
vec.clear();
pre_dfs(i, -1);
dfs(i, -1, d1);
int rt1 = i;
for(auto v: vec)if(d1[v] > d1[rt1])rt1 = v;
dfs(rt1, -1, d1);
int rt2 = i;
for(auto v: vec)if(d1[v] > d1[rt2])rt2 = v;
dfs(rt2, -1, d2);
ans = max(ans, d1[rt2]);
int mn = INF;
for(auto v: vec){
mn = min(mn, max(d1[v], d2[v]));
}
hdm.push_back(mn);
}
sort(hdm.rbegin(), hdm.rend());
if(hdm.size() >= 2)ans = max(ans, hdm[0] + hdm[1] + L);
if(hdm.size() >= 3)ans = max(ans, hdm[1] + hdm[2] + 2*L);
return ans;
}
