#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5+5;
vector<pii> adj[N];
vector<int> members;
bool vis[N];
void dfs0(int nd, int pr){
vis[nd] = 1;
members.push_back(nd);
for (auto [to, w]: adj[nd])
if (to != pr)
dfs0(to, nd);
}
int max_weight, endpoint, dp[N];
void dfs(int nd, int pr, int weight){
if (weight > max_weight){
max_weight = weight;
endpoint = nd;
}
dp[nd] = max(dp[nd], weight);
for (auto [to, w]: adj[nd])
if (to != pr)
dfs(to, nd, weight+w);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for (int i = 0; i < m; i++){
int u = A[i], v = B[i], w = T[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> roots;
for (int i = 0; i < n; i++)
if (!vis[i]){
dfs0(i, -1);
roots.push_back(i);
}
assert(roots.size() == 2);
vector<int> d;
int sum = L;
for (auto root: roots){
members.clear();
dfs0(root, -1);
max_weight = 0;
dfs(root, -1, 0);
int a = endpoint;
max_weight = 0;
dfs(endpoint, -1, 0);
int b = endpoint;
d.push_back(max_weight);
dfs(a, -1, 0);
dfs(b, -1, 0);
int value = 0;
for (auto member: members)
if (value > dp[member])
value = dp[member];
sum += value;
}
return max(sum, max(d[0], d[1]));
}
