#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5;
vector<pair<int, int>> ad[mxN];
bool vis[mxN];
int dp[mxN][2];
int mn = 1e9;
int ans = 0;
void dfs(int node) {
vis[node] = true;
for (auto [child, w] : ad[node]) {
if (vis[child]) continue;
dfs(child);
if (dp[child][1] + w >= dp[node][1]) {
dp[node][0] = dp[node][1];
dp[node][1] = dp[child][1] + w;
} else if (dp[child][1] + w > dp[node][0]) {
dp[node][0] = dp[child][1] + w;
}
}
ans = max(ans, dp[node][1] + dp[node][0]);
}
void dfs1(int node, int par, int cur) {
mn = min(mn, max(cur, dp[node][1]));
for (auto [child, w] : ad[node]) {
if (child == par) continue;
dfs1(child, node, max(cur, (dp[node][1] == dp[child][1] + w ? dp[node][0] : dp[node][1])) + w);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for (int i = 0; i < m; i++) {
ad[a[i]].push_back({b[i], t[i]});
ad[b[i]].push_back({a[i], t[i]});
}
vector<int> v;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i);
mn = 1e9;
dfs1(i, -1, 0);
v.push_back(mn);
}
}
sort(v.rbegin(), v.rend());
if (v.size() >= 1) {
ans = max(ans, v[0]);
}
if (v.size() >= 1) {
ans = max(ans, v[0] + v[1] + l);
}
if (v.size() >= 2) {
ans = max(ans, v[1] + v[2] + 2 * l);
}
return ans;
}
