#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9;
int dist[2][MAXN];
bool vis[MAXN];
vector<pair<int,int>> adj[MAXN];
vector<int> cr;
int c = 0;
void dfs(int x, int p, bool flag){
vis[x] = true;
if (flag) cr.push_back(x);
for (auto v : adj[x]){
auto [u, w] = v;
if (u == p) continue;
dist[c][u] = dist[c][x] + w;
dfs(u,x,flag);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i<N; i++){
dist[0][i] = INF;
dist[1][i] = INF;
vis[i] = false;
}
for (int i = 0; i<M; i++){
int a = A[i];
int b = B[i];
int w = T[i];
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
//dfs i -> 0
int overall = -1;
vector<int> radd;
for (int i = 0; i<N; i++){
if (!vis[i]){
dist[c][i] = 0;
dfs(i,-1,1);
int v = i;
for (auto u : cr){
if (dist[c][u] > dist[c][v]){
v = u;
}
}
dist[c][v] = 0;
dfs(v,-1,0);
int u = i;
for (auto qq : cr){
if (dist[c][qq] > dist[c][u]){
u = qq;
}
}
int diam = dist[0][u];
overall = max(overall, diam);
c = 1;
dist[c][u] = 0;
dfs(u, -1, 0);
c = 0;
int bst = INF;
int idx = -1;
for (auto qq : cr){
int one = max(dist[0][qq], dist[1][qq]);
if (one < bst){
bst = one;
idx = qq;
}
}
radd.push_back(bst);
cr.clear();
}
}
sort(radd.begin(),radd.end());
reverse(radd.begin(), radd.end());
int k = radd.size();
if (k >= 2){
overall = max(overall,radd[0] + L + radd[1]);
}
if (k >= 3){
overall = max(overall,radd[1] + L + radd[2] + L);
}
for (int i = 0; i<N; i++) adj[i].clear();
return overall;
}
