#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
vector<pair<int, int>> adj[maxN];
bool flag[maxN];
pair<int, int> max1[maxN];
int max2[maxN];
int depth[maxN];
void dfs1(int u, int p) {
flag[u] = true;
max1[u] = make_pair(0, u);
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (v != p) {
dfs1(v, u);
max1[u] = max(max1[u], make_pair(max1[v].first + w, max1[v].second));
}
}
}
int dfs2(int u, int p) {
max2[u] = max(max2[u], depth[u]);
int res = max2[u];
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (v != p) {
depth[v] = depth[u] + w;
res = min(res, dfs2(v, u));
}
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
int res = 0;
vector<int> mins;
for (int i = 0; i < N; i++) {
if (flag[i]) {
continue;
}
dfs1(i, -1);
int x = max1[i].second;
dfs1(x, -1);
int y = max1[x].second;
res = max(res, max1[x].first);
depth[x] = 0;
dfs2(x, -1);
depth[y] = 0;
mins.push_back(dfs2(y, -1));
}
sort(mins.begin(), mins.end(), greater<>());
if ((int)mins.size() >= 2) {
res = max(res, mins[0] + mins[1] + L);
}
if ((int)mins.size() >= 3) {
res = max(res, mins[1] + mins[2] + L * 2);
}
return res;
}
