#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
typedef vector<int> vi;
constexpr int MAXN = 1e5 + 10;
inline bool smin(int &l, int r) {
if (r < l) return l = r , true;
return false;
}
inline bool smax(int &l, int r) {
if (l < r) return l = r, true;
return false;
}
vi adj[MAXN];
int res, pd[MAXN], dpU[MAXN], dpD[MAXN];
int a[MAXN], b[MAXN], t[MAXN];
void dfsD(int v, int par = -1) {
dpD[v] = 0;
for (auto e : adj[v]) {
int u = a[e] ^ b[e] ^ v;
if (u ^ par) {
dfsD(u , v);
smax(dpD[v] , dpD[u] + t[e]);
}
}
}
void dfsU(int v, int& root, int par = -1) {
pd[v] = max(dpD[v] , dpU[v]);
if (pd[v] < pd[root]) root = v;
smax(res , pd[v]);
auto solve = [&]() {
int worst = dpU[v];
for (auto e : adj[v]) {
int u = a[e] ^ b[e] ^ v;
if (u ^ par) {
smax(dpU[u] , worst + t[e]);
smax(worst , dpD[u] + t[e]);
}
}
};
solve();
reverse(all(adj[v]));
solve();
for (auto e :adj[v]) {
int u = a[e] ^ b[e] ^ v;
if (u ^ par)
dfsU(u , root , v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
rep(i , 0 , N) adj[i].clear();
rep(i , 0 , M) {
tie(a[i] , b[i] , t[i]) = make_tuple(A[i] ,B[i] ,T[i]);
adj[A[i]].pb(i);
adj[B[i]].pb(i);
}
memset(pd , 0 , sizeof(pd));
memset(dpU , 0 , sizeof(dpU));
memset(dpD , 0 , sizeof(dpD));
res = 0;
vi vec;
rep(i , 0 , N)
if (!pd[i]) {
int root = i;
dfsD(i);
dfsU(i , root);
vec.pb(root);
}
sort(all(vec) , [](int l , int r) { return pd[l] > pd[r]; });
int lres = 1e9;
int g = min(3 , (int)vec.size());
rep(i , 0 , g) {
int worst = 0;
rep(j , 0 , g)
if (i ^ j) {
smax(worst , pd[vec[i]] + pd[vec[j]] + L);
rep(z , 0 , g)
if (z ^ i && z ^ j)
smax(worst , pd[vec[z]] + pd[vec[j]] + 2 * L);
}
smin(lres , worst);
}
return max(lres , res);
}
