#include "dreaming.h"
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (1 << 30) - 1;
const ll LINF = (1LL << 60) - 1LL;
vector<vector<P>> G;
vector<int> dep, dp, vis;
vector<multiset<int>> st;
void build(int i, int p, int d) {
vis[i] = 1;
dep[i] = d;
dp[i] = dep[i];
for (auto &e : G[i]) {
if (e.first == p) {
continue;
}
build(e.first, i, d + e.second);
dp[i] = max(dp[i], dp[e.first]);
st[i].insert(dp[e.first] - dep[i]);
}
}
pair<int, int> calc(int i, int p) {
int res = INF, dia = 0;
if (st[i].size() > 0) {
auto itr = st[i].end();
--itr;
res = (*itr);
}
if (st[i].size() > 1) {
auto itr = st[i].end();
--itr;
dia += (*itr);
// cout << i << " " << (*itr) << endl;
--itr;
dia += (*itr);
// cout << i << " " << (*itr) << endl;
}
for (auto &e : G[i]) {
if (e.first == p) {
continue;
}
int t = dp[e.first] - dep[i];
st[i].erase(st[i].find(t));
if (st[i].size() > 0) {
auto it = st[i].end();
--it;
st[e.first].insert((*it) + e.second);
} else {
st[e.first].insert(e.second);
}
pair<int, int> re = calc(e.first, i);
res = min(res, re.first);
dia = max(dia, re.second);
st[i].insert(t);
}
// cout << i << " " << res << endl;
return make_pair(res, dia);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
G.resize(N);
st.resize(N);
dep.resize(N);
dp.resize(N);
vis.resize(N);
for (int i = 0; i < M; i++) {
G[A[i]].push_back(P(B[i], T[i]));
G[B[i]].push_back(P(A[i], T[i]));
}
vector<ll> s;
ll ma = 0;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
if (G[i].size() == 0) {
s.push_back(0);
continue;
}
build(i, -1, 0);
pair<int, int> re = calc(i, -1);
ma = max(ma, (ll)re.second);
// cout << re.second << endl;
s.push_back(re.first);
}
}
sort(all(s));
reverse(all(s));
ll ans = ma;
if (s.size() > 1) {
ans = max(ans, s[0] + s[1] + L);
}
if (s.size() > 2) {
ans = max(ans, s[1] + s[2] + 2LL * L);
}
return ans;
}
