// looking to shine brighter in this world...
#define TASK "dreaming"
#include "dreaming.h"
#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)
template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }
const bool __initialization = []() {
cin.tie(nullptr)->sync_with_stdio(false);
if (fopen(TASK".inp", "r")) {
(void)(!freopen(TASK".inp", "r", stdin));
(void)(!freopen(TASK".out", "w", stdout)); }
cout << setprecision(12) << fixed;
return true;
}();
constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;
// ================================================================================
constexpr int maxn = 1e5 + 5;
struct Edge { int v, c; };
int n, ne, cost;
vector<Edge> g[maxn];
int vis[maxn];
int timer;
// largest / second largest
int fi[maxn], se[maxn];
void DfsDown(int u, int p) {
vis[u] = timer;
Fe (&[v, c] : g[u]) {
if (v == p) continue;
DfsDown(v, u);
if (fi[u] < fi[v] + c) {
tie(fi[u], se[u]) = pair(fi[v] + c, fi[u]);
}
else {
chmax(se[u], fi[v] + c);
}
}
}
int radius[maxn];
void DfsUp(int u, int p) {
Fe (&[v, c] : g[u]) {
if (v == p) continue;
radius[v] = max(radius[u],
(fi[u] == fi[v] + c) ? se[u] : fi[u]) + c;
DfsUp(v, u);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
{ n = N; ne = M; cost = L; }
Rep (i, ne) {
int u = A[i], v = B[i], c = T[i];
g[u].push_back({ v, c });
g[v].push_back({ u, c });
}
Rep (u, n) {
if (!vis[u]) {
++timer;
DfsDown(u, -1);
DfsUp(u, -1);
}
}
Rep (u, n) chmax(fi[u], radius[u]);
vector<int> a(timer + 1, inf);
Rep (u, n) chmin(a[vis[u]], fi[u]);
fi[n] = [&a, L]() {
if (timer == 1) return a[1];
if (timer == 2) return a[1] + a[2] + L;
sort(1 + all(a), greater<int>());
int ret = inf;
array<array<int, 3>, 3> perm {{
{{ 1, 2, 3 }},
{{ 2, 1, 3 }},
{{ 3, 1, 2 }}
}};
Fe (&[x, y, z] : perm) {
int get = max({
a[x] + a[y] + L,
a[x] + a[z] + L,
a[y] + a[z] + 2 * L
});
chmin(ret, get);
}
return ret;
}();
return *max_element(fi, fi + n + 1);
}
