#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> p, s;
int findp(int a){
if (p[a] == a) return p[a];
return p[a] = findp(p[a]);
}
void merge(int a, int b){
a = findp(a);
b = findp(b);
if (a == b) return;
p[b] = a;
s[a] += s[b];
s[b] == 0;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
p.resize(N);
for (int i=0; i<N; i++) p[i] = i;
s.resize(N, 1);
vector<vector<pair<int,int>>> g(N);
for (int i=0; i<M; i++){
merge(A[i], B[i]);
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<int> dm, r;
vector<bool> done(N, false), seen(N, false);
vector<int> tp(N, -1), td(N);
for (int i=0; i<N; i++){
int j = findp(i);
if (done[j]) continue;
done[j] = true;
if (s[j] == 1){
dm.push_back(0);
r.push_back(0);
continue;
}
queue<pair<int,int>> q;
q.push({j, 0});
int ft = j, md = 0;
while (!q.empty()){
int cur = q.front().first, d = q.front().second;
q.pop();
if (seen[cur]) continue;
seen[cur] = true;
if (d > md){
md = d;
ft = cur;
}
for (pair<int,int> next : g[cur]) q.push({next.first, d+next.second});
}
tp[ft] = ft;
td[ft] = 0;
int ft2 = ft;
md = 0;
q.push({ft, 0});
while (!q.empty()){
int cur = q.front().first, d = q.front().second;
q.pop();
td[cur] = d;
if (d > md){
md = d;
ft2 = cur;
}
for (pair<int,int> next : g[cur]){
if (tp[next.first] == -1){
tp[next.first] = cur;
q.push({next.first, d+next.second});
}
}
}
dm.push_back(md);
int br = md;
while (ft2 != ft){
br = min(br, max(td[ft2], md-td[ft2]));
ft2 = tp[ft2];
}
r.push_back(br);
}
int res = 0;
for (int x : dm) res = max(res, x);
if (r.size() == 2) res = max(res, r[0]+r[1]+L);
else {
sort(r.begin(), r.end());
res = max(res, r[r.size()-1]+r[r.size()-2]+L);
res = max(res, r[r.size()-2]+r[r.size()-3]+2*L);
}
return res;
}
