#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
vector<array<int, 2>> adj[100000];
int a[100000], b, x, y, ans = -1;
bitset<100000> vis;
void dfs(int u, int d, int p = -1){
vis[u] = 1;
a[u] = max(a[u], d);
if(d > x) x = d, y = u;
if(d < 0) b = min(b, a[u]);
for(auto &v : adj[u]) if(v[0] != p) dfs(v[0], d < 0 ? d : d + v[1], u);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]){
for(int i = 0; i < m; i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
priority_queue<int> q;
for(int i = 0; i < n; i++){
if(vis[i]) continue;
x = y = -1, b = INT_MAX;
dfs(i, 0); dfs(y, 0); dfs(y, 0);
ans = max(ans, x);
dfs(i, -1);
q.push(-b);
while(q.size() > 3) q.pop();
}
int op3 = -q.top(); q.pop();
if(q.empty()) return ans;
int op2 = -q.top(); q.pop();
if(q.empty()) return max(ans, op2 + op3 + L);
int op1 = -q.top(); q.pop();
return max(ans, max(op1 + op2 + L, op2 + op3 + L + L));
}
