#include "dreaming.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++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;
vector<pll> A[N];
bool vis[N];
int par[N];
ll dis[N];
void dfs_vis(int v)
{
vis[v] = 1;
for (auto [u, _] : A[v]) {
if (!vis[u])
dfs_vis(u);
}
}
pll dfs_farthest(int v, int p, ll h)
{
pll ans = {h, v};
par[v] = p;
dis[v] = h;
for (auto [u, w] : A[v]) {
if (u != p)
ans = max(ans, dfs_farthest(u, v, h+w));
}
return ans;
}
int travelTime(int n, int m, int L, int V[], int U[], int W[])
{
Loop (i,0,m) {
int v = V[i], u = U[i], w = W[i];
A[v].push_back({u,w});
A[u].push_back({v,w});
}
vector<ll> vec;
ll ans = 0;
Loop (v,0,n) {
if (vis[v])
continue;
dfs_vis(v);
int u = dfs_farthest(v, -1, 0).second;
u = dfs_farthest(u, -1, 0).second;
ll rad = LONG_LONG_MAX;
ll dia = dis[u];
ans = max(ans, dia);
while (u != -1) {
rad = min(rad, max(dis[u], dia-dis[u]));
u = par[u];
}
vec.push_back(rad);
}
sort(vec.begin(), vec.end());
if (vec.size() >= 2)
ans = max(ans, vec.end()[-1] + vec.end()[-2] + L);
if (vec.size() >= 3)
ans = max(ans, vec.end()[-2] + vec.end()[-3] + L + L);
return ans;
}
