#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr size_t N = 100000;
vector<pair<size_t, size_t>> g[N];
size_t f[N][2], c[N];
bitset<N> visited;
void update_state(size_t u, size_t d, size_t v)
{
if (d >= f[u][0])
f[u][1] = f[u][0], f[u][0] = d, c[u] = v;
else if (d > f[u][1])
f[u][1] = d;
}
void calc1(size_t u)
{
f[u][0] = f[u][1] = 0;
c[u] = SIZE_MAX;
visited[u] = 1;
for (auto const &[v, w] : g[u])
if (!visited[v])
{
calc1(v);
update_state(u, f[v][0] + w, v);
}
}
void calc2(size_t u, size_t p)
{
for (auto const &[v, w] : g[u])
if (v != p)
{
if (v == c[u])
update_state(v, f[u][1] + w, u);
else
update_state(v, f[u][0] + w, u);
calc2(v, u);
}
}
size_t find_min_max(size_t u, size_t p)
{
size_t ans = max(f[u][0], f[u][1]);
for (auto const &[v, w] : g[u])
if (v != p)
ans = min(ans, find_min_max(v, u));
return ans;
}
size_t find_diameter(size_t u, size_t p)
{
size_t ans = f[u][0] + f[u][1];
for (auto const &[v, w] : g[u])
if (v != p)
ans = max(ans, find_diameter(v, u));
return ans;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for (size_t i = 0; i < m; i++)
{
g[a[i]].emplace_back(b[i], t[i]);
g[b[i]].emplace_back(a[i], t[i]);
}
vector<int> distances;
int max_diameter = 0;
for (size_t i = 0; i < n; i++)
{
if (!visited[i])
{
calc1(i);
calc2(i, SIZE_MAX);
distances.push_back(find_min_max(i, SIZE_MAX) + l);
max_diameter = max<int>(max_diameter, find_diameter(i, SIZE_MAX));
}
}
sort(distances.begin(), distances.end(), greater<int>());
if (distances.size() >= 2)
max_diameter = max(max_diameter, distances[0] + distances[1] - l);
if (distances.size() >= 3)
max_diameter = max(max_diameter, distances[1] + distances[2]);
return max_diameter;
}
