#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MN = 1e5 + 5;
vector<pair<int, int>> adj[MN];
bool explored[MN];
vector<int> dia, dist;
multimap<int, int> m[MN];
int dp[MN];
int dfs(int v, int p = -1, int last = 0) {
int val = max(last, dp[v]);
for (auto i : adj[v]) {
if (i.first == p)
continue;
auto itr = m[v].rbegin();
if (itr->second == i.first && m[v].size() == 1)
val = min(val, dfs(i.first, v, last + i.second));
else if (itr->second == i.first)
val = min(val, dfs(i.first, v, max(last, (++itr)->first) + i.second));
else
val = min(val, dfs(i.first, v, max(last, itr->first) + i.second));
}
dp[v] = max(dp[v], last);
return val;
}
void pre(int v) {
explored[v] = true;
for (auto i : adj[v]) {
if (!explored[i.first])
pre(i.first), m[v].insert({dp[i.first] + i.second, i.first});
}
dp[v] = m[v].empty() ? 0 : m[v].rbegin()->first;
}
pair<int, int> longest(int v, int p = -1) {
pair<int, int> ans = {0, v};
for (auto i : adj[v]) {
if (i.first == p)
continue;
auto temp = longest(i.first, v);
ans = max(ans, {temp.first + i.second, temp.second});
}
return ans;
}
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]);
}
for (int i = 0; i < N; i++) {
if (!explored[i]) {
pre(i), dist.push_back(dfs(i));
auto temp = longest(i);
dia.push_back(longest(temp.second).first);
}
}
sort(dist.begin(), dist.end(), greater<>());
int ans = *max_element(dia.begin(), dia.end());
if (dist.size() > 1)
ans = max(ans, dist[0] + dist[1] + L);
return ans;
}
