#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/infty.hpp"
template <typename T, T Div = 2> constexpr T infty = std::numeric_limits<T>::max() / Div;
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 2 "library2/utility/rec_lambda.hpp"
template <class F> class RecursiveLambda {
F f;
public:
explicit constexpr RecursiveLambda(F &&f_) : f(std::forward<F>(f_)) {}
template <class... Args> constexpr auto operator()(Args &&...args) const {
return f(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F &&f) {
return RecursiveLambda<F>(std::forward<F>(f));
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 3 "library2/utility/revrep.hpp"
class ReversedRange {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
--itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr ReversedRange(const int f, const int l) noexcept
: first(l - 1), last(std::min(f, l) - 1) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr ReversedRange revrep(const int l, const int r) noexcept {
return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
return ReversedRange(0, n);
}
#line 2 "library2/utility/setmax.hpp"
template <typename T> bool setmax(T &lhs, const T &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
#line 2 "library2/utility/setmin.hpp"
template <typename T> bool setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
#line 10 "paper.cpp"
#include "dreaming.h"
struct Edge {
int to;
int cost;
};
int N, M, L;
int C;
std::vector<int> A, B, T;
std::vector<std::vector<Edge>> forest;
std::vector<int> components_radius, components_diameter;
void decompose() {
std::vector<bool> used(N);
std::vector<std::vector<int>> depths(N);
auto dfs =
rec_lambda([&](auto &&f, const int v, const int p, std::vector<int> &vertices) -> int {
vertices.push_back(v);
used[v] = true;
const int c = len(forest[v]);
if (c == 0) {
return 0;
}
depths[v].resize(c);
for (const int i : rep(c)) {
if (forest[v][i].to == p) {
depths[v][i] = 0;
} else {
depths[v][i] = f(forest[v][i].to, v, vertices) + forest[v][i].cost;
}
}
return *std::max_element(depths[v].begin(), depths[v].end());
});
std::vector<int> parent_depth(N);
auto reroot = rec_lambda([&](auto &&f, const int v, const int p, const int d) -> void {
parent_depth[v] = d;
const int c = len(forest[v]);
if (c == 0) {
return;
}
std::vector<int> l_max(c + 1), r_max(c + 1);
for (const int i : rep(c)) {
l_max[i + 1] = std::max(l_max[i], depths[v][i]);
}
for (const int i : revrep(c)) {
r_max[i] = std::max(r_max[i + 1], depths[v][i]);
}
for (const int i : rep(c)) {
if (forest[v][i].to == p) {
continue;
}
f(forest[v][i].to, v, std::max({d, l_max[i], r_max[i + 1]}) + forest[v][i].cost);
}
});
for (const int i : rep(N)) {
if (used[i]) {
continue;
}
std::vector<int> vertices;
dfs(i, N, vertices);
reroot(i, N, 0);
auto get_radius = [&]() {
if (len(vertices) == 1) {
return 0;
}
int res = infty<int>;
for (const int v : vertices) {
setmin(res, std::max(parent_depth[v],
*std::max_element(depths[v].begin(), depths[v].end())));
}
return res;
};
auto get_diameter = [&]() {
if (len(vertices) == 1) {
return 0;
}
int res = -infty<int>;
for (const int v : vertices) {
setmax(res, std::max(parent_depth[v],
*std::max_element(depths[v].begin(), depths[v].end())));
}
return res;
};
components_radius.push_back(get_radius());
components_diameter.push_back(get_diameter());
}
C = len(components_radius);
}
int solve() {
decompose();
const int max_diameter =
*std::max_element(components_diameter.begin(), components_diameter.end());
if (C == 1) {
return max_diameter;
}
if (C == 2) {
return std::max(components_radius[0] + components_radius[1] + L, max_diameter);
}
const int max_radius = *std::max_element(components_radius.begin(), components_radius.end());
auto find_second = [&]() {
components_radius.erase(
std::max_element(components_radius.begin(), components_radius.end()));
return *std::max_element(components_radius.begin(), components_radius.end());
};
auto find_third = [&]() {
// find_second is used
components_radius.erase(
std::max_element(components_radius.begin(), components_radius.end()));
return *std::max_element(components_radius.begin(), components_radius.end());
};
const int second_radius = find_second();
const int third_radius = find_third();
return std::max(
{max_diameter, max_radius + second_radius + L, second_radius + third_radius + 2 * L});
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
N = n;
M = m;
L = l;
A.resize(M);
B.resize(M);
T.resize(M);
forest.resize(N);
for (const int i : rep(M)) {
A[i] = a[i];
B[i] = b[i];
T[i] = t[i];
forest[A[i]].push_back({B[i], T[i]});
forest[B[i]].push_back({A[i], T[i]});
}
return solve();
}
/*
int main() {
int n, m, l;
int a[20], b[20], t[20];
std::cin >> n >> m >> l;
for (const int i : rep(m)) {
std::cin >> a[i] >> b[i] >> t[i];
}
std::cout << travelTime(n, m, l, a, b, t) << std::endl;
}
*/
