#include "dreaming.h"

#include <bits/stdc++.h>

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    if (n == 1) {
        return 0;
    }
    // if (n == 2) {
    //     if (m == 0) {
    //         return L;
    //     }
    //     return T[0];
    // }
    std::vector<std::vector<std::pair<int, int>>> gr(n);
    for (int i = 0; i < m; i++) {
        gr[A[i]].push_back({B[i], T[i]});
        gr[B[i]].push_back({A[i], T[i]});
    }

    int ans = 0;
    std::vector<bool> used(n);
    std::vector<int> dist(n), prv(n);
    std::vector<int> cum;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            std::vector<int> vec;
            auto dfs = [&](auto dfs, int v, int f, int d) -> void {
                used[v] = true;
                dist[v] = d;
                vec.push_back(v);
                for (auto [t, w] : gr[v]) {
                    if (t != f) {
                        dfs(dfs, t, v, d + w);
                    }
                }
            };
            dfs(dfs, i, -1, 0);
            int it = *std::max_element(vec.begin(), vec.end(), [&](int a, int b) { return dist[a] < dist[b]; });
            auto dfs2 = [&](auto dfs2, int v, int f, int d) -> void {
                dist[v] = d;
                prv[v] = f;
                for (auto [t, w] : gr[v]) {
                    if (t != f) {
                        dfs2(dfs2, t, v, d + w);
                    }
                }
            };
            dfs2(dfs2, it, -1, 0);
            int fr = *std::max_element(vec.begin(), vec.end(), [&](int a, int b) { return dist[a] < dist[b]; });
            int u = fr;
            int res = dist[fr];
            while (u != it) {
                res = std::min(res, std::max(dist[u], dist[fr] - dist[u]));
                u = prv[u];
            }
            ans = std::max(ans, dist[fr]);
            cum.push_back(res);
        }
    }
    std::sort(cum.begin(), cum.end());
    if (cum.size() > 1) {
        ans = std::max(ans, cum.rbegin()[1] + cum.back() + L);
    }
    if (cum.size() > 2) {
        ans = std::max(ans, cum.rbegin()[1] + cum.rbegin()[2] + 2 * L);
    }
    return ans;
}