#include <dreaming.h>
#include <bits/stdc++.h>
using namespace std;
int travelTime(int n, int m, int cost, int A[], int B[], int T[]) {
int ans = 0, t = 0;
vector<int> seen(n), dpu(n), dpb(n), cn;
vector<vector<int>> pref(n), suf(n);
deque<pair<int, int>> cur;
vector<vector<pair<int, int>>> G(n);
for (int i = 0; i < m; ++i) {
G[A[i]].emplace_back(B[i], T[i]);
G[B[i]].emplace_back(A[i], T[i]);
}
function<void(int, int)> dfs = [&](int node, int last) {
cn.emplace_back(node);
seen[node] = t;
pref[node].emplace_back(0), suf[node].emplace_back(0);
for (auto x : G[node])
if (x.first != last) {
dfs(x.first, node);
dpb[node] = max(dpb[node], dpb[x.first] + x.second);
pref[node].emplace_back(dpb[x.first] + x.second);
suf[node].emplace_back(dpb[x.first] + x.second);
}
pref[node].emplace_back(0), suf[node].emplace_back(0);
int s = pref[node].size() - 1;
for (int i = 1; i <= s; ++i)
pref[node][i] = max(pref[node][i], pref[node][i - 1]);
for (int i = s; i; --i)
suf[node][i] = max(suf[node][i], suf[node][i + 1]);
};
function<void(int, int)> dfs2 = [&](int node, int last) {
int ct = 1;
for (auto x : G[node])
if (x.first != last) {
dpu[x.first] = x.second + max(max(pref[node][ct - 1], suf[node][ct + 1]), dpu[node]);
dfs2(x.first, node);
++ct;
}
};
for (int i = 0; i < n; ++i)
if (!seen[i]) {
++t;
cn.clear();
dfs(i, -1);
dfs2(i, -1);
pair<int, int> ans = {INT_MAX, 0};
//cout << "ROOT : " << i << '\n';
for (auto x : cn)
//printf("%d : U %d D %d\n", x, dpu[x], dpb[x]);
ans = min(ans, {max(dpu[x],dpb[x]),x});
cur.emplace_back(ans);
//cout << ans.first << ' ' << ans.second << '\n';
}
sort(cur.begin(), cur.end());
reverse(cur.begin(), cur.end());
pair<int, int> node = cur.front();
cur.pop_front();
for (auto [c, n] : cur) {
//cout << "ADD " << n << ' ' << node.second << '\n';
G[n].emplace_back(node.second, cost);
G[node.second].emplace_back(n, cost);
if (c < node.second)
node.first = max(node.first, c + cost);
else
node.first = max(node.first, c + cost), node.second = n;
}
dpb.assign(n, 0), dpu.assign(n, 0);
pref.assign(n, vector<int>()), suf.assign(n, vector<int>());
dfs(0, -1);
dfs2(0, -1);
for (int i = 0; i < n; ++i)
ans = max(ans, dpu[i] + dpb[i]);
return ans;
}
