#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.ST << ", " << p.ND << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
template<class T> int size(T && a) { return (int) a.size(); }
using LL = long long;
using PII = pair<int, int>;
#include "dreaming.h"
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<PII>> adj(N);
REP(i, M) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
vector<int> dst(N, -1), component;
function<void(int, bool)> get_dst = [&](int v, bool get_comp) {
if(get_comp) component.emplace_back(v);
if(dst[v] == -1) dst[v] = 0;
for(auto &[u, w] : adj[v]) {
if(dst[u] == -1) {
dst[u] = dst[v] + w;
get_dst(u, get_comp);
}
}
};
auto clear_dst = [&]() {
for(int i : component)
dst[i] = -1;
};
int inf = (int) 1e9;
vector<int> cen(N), q = {-inf, -inf};
REP(i, N) if(dst[i] == -1) {
auto get_far = [&](int x) {
clear_dst();
get_dst(x, false);
PII best = {-1, -1};
for(int j : component)
best = max(best, {dst[j], j});
return best.ND;
};
auto update_cen = [&]() {
int ret = inf;
for(int j : component) {
cen[j] = max(cen[j], dst[j]);
ret = min(ret, cen[j]);
}
return ret;
};
get_dst(i, true);
int a = get_far(i);
int b = get_far(a);
update_cen();
get_far(b);
q.emplace_back(update_cen());
component.clear();
}
sort(q.rbegin(), q.rend());
return max({q[0], q[0] + L + q[1], q[1] + 2 * L + q[2]});
}
