#include "dreaming.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
int par[N], parw[N];
vector<pii> A[N];
pii dfs(int v, int p, int w)
{
par[v] = p;
parw[v] = w;
pii ans = {0, v};
for (auto [u, w] : A[v]) {
if (u != p) {
auto tmp = dfs(u, v, w);
tmp.first += w;
ans = max(ans, tmp);
}
}
return ans;
}
int travelTime(int N, int M, int L, int V[], int U[], int T[])
{
Loop (i,0,M) {
A[V[i]].emplace_back(U[i], T[i]);
A[U[i]].emplace_back(V[i], T[i]);
}
fill(par, par+N, -2);
int ans = 0;
vector<int> vec;
Loop (v,0,N) {
if (par[v] != -2)
continue;
int dard = dfs(v, -1, 0).second;
auto [x, u] = dfs(dard, -1, 0);
int y = 0;
ans = max(ans, x);
int kooft = 2e9;
for (;;) {
kooft = min(kooft, max(x, y));
if (par[u] == -1)
break;
y += parw[u];
x -= parw[u];
u = par[u];
}
vec.push_back(kooft);
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
if (vec.size() >= 2)
ans = max(ans, L + vec[0] + vec[1]);
if (vec.size() >= 3)
ans = max(ans, L + L + vec[1] + vec[2]);
return ans;
}
