#include "dreaming.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int n, m, l;
vector<pair<int, int>> dp;
vector<vector<pair<int, int>>> g;
int dfs1(int u, int par, int c, vector<int> &cmp_of) {
cmp_of[u] = c;
for (auto [v, w] : g[u]) {
if (v == par) continue;
int time = dfs1(v, u, c, cmp_of) + w;
dp[u] = max(dp[u], max(make_pair(time, dp[u].first), make_pair(dp[u].first, time)));
}
return dp[u].first;
}
void dfs2(int u, int par, int c, vector<int> &cmp_of) {
cmp_of[u] = c;
for (auto [v, w] : g[u]) {
if (v == par) continue;
int time = (dp[u].first != dp[v].first + w ? dp[u].first : dp[u].second) + w;
dp[v] = max(dp[v], max(make_pair(time, dp[v].first), make_pair(dp[v].first, time)));
dfs2(v, u, c, cmp_of);
}
}
int solve() {
dp.resize(n, {0, 0});
vector<int> cmp_of(n, -1), longest;
for (int i = 0; i < n; i++) {
if (cmp_of[i] == -1) {
dfs1(i, -1, longest.size(), cmp_of);
longest.push_back(INF);
}
}
fill(cmp_of.begin(), cmp_of.end(), -1);
longest.clear();
int ans = 0;
for (int i = 0; i < n; i++) {
if (cmp_of[i] == -1) {
dfs2(i, -1, longest.size(), cmp_of);
longest.push_back(INF);
}
longest[cmp_of[i]] = min(longest[cmp_of[i]], dp[i].first);
ans = max(ans, dp[i].first + dp[i].second);
}
sort(longest.rbegin(), longest.rend());
if (longest.size() > 1) ans = max(ans, longest[0] + l + longest[1]);
if (longest.size() > 2) ans = max(ans, longest[1] + 2 * l + longest[2]);
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
m = M;
l = L;
g.resize(n);
for (int i = 0; i < m; i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
return solve();
}
