#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 1e5 + 5;
int N, M, L;
vector<pair<int,int>> g[MX];
bool vis[MX];
int cur = 0, mx = 0, z = 0, len = 0;
vector<int> vec;
pair<int,int> par[MX];
void dfs(int v) {
vis[v] = 1;
vec.push_back(v);
if(cur > mx) {
mx = cur;
z = v;
}
for(auto [u, w] : g[v]) {
if(!vis[u]) {
cur += w;
par[u] = {v, w};
dfs(u);
cur -= w;
}
}
}
vector<pair<int,int>> P;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
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]});
}
for(int i = 1; i <= N; i++) {
if(vis[i]) continue;
vec.clear();
cur = 0, mx = 0, z = 0, len = 0;
dfs(i);
for(auto x : vec) {
vis[x] = 0;
par[x] = {z, 0};
}
if(vec.size() == 1) {
for(auto x : vec) {
vis[x] = 1;
}
P.push_back({0, 0});
continue;
}
vec.clear();
int tz = z;
cur = 0, mx = 0, z = 0;
par[tz] = {tz, 0};
dfs(tz);
len = mx;
int k = z, sum = 0, y = 2e9, p = 0, q = 0;
while(k != tz) {
if(abs((sum) - (len - sum)) < y) {
y = abs((sum) - (len - sum));
p = sum;
q = len - sum;
}
sum += par[k].second;
k = par[k].first;
}
vec.clear();
P.push_back({max(p, q), min(p, q)});
}
sort(P.rbegin(), P.rend());
int ans = 0;
for(auto [x, y] : P) {
ans = max(ans, x + y);
}
if(P.size() > 1) {
ans = max(ans, P[0].first + L + P[1].first);
}
if(P.size() > 2) {
ans = max(ans, P[1].first + 2 * L + P[2].first);
}
return ans;
}
/*
int aa[100], bb[100], cc[100];
int main() {
aa[0] = 1, bb[0] = 2, cc[0] = 1;
aa[1] = 2, bb[1] = 3, cc[1] = 4;
aa[2] = 4, bb[2] = 5, cc[2] = 5;
aa[3] = 5, bb[3] = 6, cc[3] = 7;
aa[4] = 7, bb[4] = 8, cc[4] = 3;
aa[5] = 8, bb[5] = 9, cc[5] = 4;
cout << travelTime(9, 6, 3, aa, bb, cc) << '\n';
}
*/
