#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5+5;
int ans;
int fix[N];
vector <int> roots;
vector <vector<pair<int,int>>> v(N);
int d[N];
int d1[N];
int d2[N];
vector <int> res;
void dfs(int x) {
res.push_back(x);
fix[x] = 1;
for (auto [to,w]:v[x]) {
if (fix[to]) continue;
d[to] = d[x] + w;
dfs(to);
}
}
void dfs1(int x, int p) {
for (auto [to,w]:v[x]) {
if (to == p) continue;
d1[to] = d1[x] + w;
dfs1(to,x);
}
}
void dfs2(int x, int p) {
for (auto [to,w]:v[x]) {
if (to == p) continue;
d2[to] = d2[x] + w;
dfs2(to,x);
}
}
int get(int x, int n) {
res.clear();
dfs(x);
int node1 = 0;
for (auto i:res) {
if (d[node1] < d[i]) node1 = i;
}
dfs1(node1,node1);
int node2 = 0;
for (auto i:res) {
if (d1[node2] < d1[i]) node2 = i;
}
dfs2(node2,node2);
int mn = INT_MAX;
for (auto i:res) {
mn = min(mn,max(d1[i],d2[i]));
}
return mn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
ans = 0;
for (int i = 0; i < M; i++) {
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for (int i = 0; i < N; i++) {
if (fix[i]) continue;
roots.push_back(get(i,N));
}
sort(roots.begin(),roots.end(),greater<int>());
if (roots.size() >= 2) {
ans = max(ans, roots[0] + roots[1] + L);
}
if (roots.size() > 2) {
ans = max(ans,roots[1]+roots[2]+2*L);
}
return ans;
}
