#include "dreaming.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK "DREAMING"
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 7;
long long dp[N][2], g[N], d[N], ans;
pair <long long, int> center_dist;
vector <pair <int, int>> a[N];
bool visited[N];
int n, m, l;
void dfs1(int u, int p) {
visited[u] = 1;
for (auto i : a[u]) {
if (i.fi == p) continue;
int v = i.fi, w = i.se;
dfs1(v, u);
if (dp[u][0] < dp[v][0] + w) {
dp[u][1] = dp[u][0];
dp[u][0] = dp[v][0] + w;
} else if (dp[v][0] + w > dp[u][1])
dp[u][1] = dp[v][0] + w;
}
maxi(ans, dp[u][0] + dp[u][1]);
}
void dfs2(int u, int p, long long w) {
if (p != u) g[u] = max(g[p] + w, (dp[u][0] + w == dp[p][0] ? (dp[p][1] + w) : dp[p][0]));
mini(center_dist, mp(max(g[u], dp[u][0]), u));
for (auto i : a[u]) {
if (i.fi == p) continue;
int v = i.fi, w2 = i.se;
dfs2(v, u, w2);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
m = M;
l = L;
for (int i = 0; i < m; ++i) {
int u = ++A[i], v = ++B[i], w = T[i];
a[u].push_back({v, w});
a[v].push_back({u, w});
}
vector <pair <long long, int>> v;
for (int i = 1; i <= n; ++i) {
if (visited[i] == 1) continue;
dfs1(i, i);
center_dist = mp(1e9 + 9, 0);
dfs2(i, i, 0);
v.push_back(center_dist);
}
sort(all(v), greater <pair <long long, int>>());
for (int i = 1; i < v.size(); ++i) {
a[v[0].se].emplace_back(v[i].se, l);
a[v[i].se].emplace_back(v[0].se, l);
}
memset(dp, 0, sizeof dp);
ans = 0;
dfs1(1, 1);
return ans;
}
