#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 1e5+5;
vector <pair <int, ll>> adj[mxN];
int n, m, vis[mxN];
ll dp[mxN];
void dfs(int u, int p) {
dp[u] = 0;
vis[u] = 1;
for (auto [v, w] : adj[u]) if (v != p) {
dfs(v, u);
dp[u] = max(dp[u], dp[v] + w);
}
}
vector <ll> ans;
void dfs2(int u, int p, ll L) {
vis[u] = 1;
ll T = max(L, dp[u]);
ans.back() = min(ans.back(), T);
vector <pair <ll, int>> a;
a.emplace_back(L, -1);
for (auto [v, w] : adj[u]) if (v != p) {
a.emplace_back(dp[v] + w, v);
sort(a.rbegin(), a.rend());
while (a.size() > 2) a.pop_back();
}
for (auto [v, w] : adj[u]) if (v != p) {
dfs2(v, u, (a[0].second == v ? a[1].first : a[0].first) + w);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M;
for (int i = 0; i < m; i++) adj[A[i]].emplace_back(B[i], T[i]), adj[B[i]].emplace_back(A[i], T[i]);
for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, i);
for (int i = 0; i < n; i++) vis[i] = 0;
for (int i = 0; i < n; i++) if (!vis[i]) ans.emplace_back(INT_MAX), dfs2(i, i, 0);
sort(ans.rbegin(), ans.rend());
if (ans.size() == 1) return ans[0];
else if (ans.size() == 2) return ans[0] + ans[1] + L;
else return max(ans[0] + ans[1] + L, ans[1] + ans[2] + 2*L);
}
