#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vector<vector<array<int, 2>>> graph(n);
for(int i = 0; i < m; i ++)
graph[a[i]].push_back({b[i], t[i]}), graph[b[i]].push_back({a[i], t[i]});
vector<int> d;
vector<array<int, 2>> lnk(n, {-1, -1});
vector<bool> used(n);
int res = 0;
for(int i = 0; i < n; i ++){
if(!used[i]){
set<array<int, 2>> st;
st.insert({0, i});
used[i] = 1;
int last = -1;
while(!st.empty()){
auto [x, y] = *st.begin();
st.erase(st.begin());
last = y;
for(auto z : graph[y]){
if(!used[z[0]]){
st.insert({x + z[1], z[0]});
used[z[0]] = 1;
}
}
}
used[last] = 0;
st.insert({0, last});
while(!st.empty()){
auto [x, y] = *st.begin();
st.erase(st.begin());
last = y;
for(auto z : graph[y]){
if(used[z[0]]){
lnk[z[0]] = {y, z[1]};
st.insert({x + z[1], z[0]});
used[z[0]] = 0;
}
}
}
used[i] = 1;
st.insert({0, i});
while(!st.empty()){
auto [x, y] = *st.begin();
st.erase(st.begin());
for(auto z : graph[y]){
if(!used[z[0]]){
st.insert({x + z[1], z[0]});
used[z[0]] = 1;
}
}
}
vector<int> p;
int sum = 0;
while(lnk[last][0] != -1){
p.push_back(lnk[last][1]);
sum += p.back();
last = lnk[last][0];
}
res = max(res, sum);
p.push_back(0);
int ans = 1e9, s = 0;
for(int i = 0; i < (int)p.size(); i ++)
ans = min(ans, max(s, sum - s)), s += p[i];
d.push_back(ans);
}
}
if(d.size() == 1)
return res;
else if(d.size() == 2)
return max(res, d[0] + d[1] + l);
else{
sort(d.begin(), d.end());
int ans = 2e9;
int k = d.size();
for(int i = 0; i < k - 2; i ++)
ans = min(ans, max({res, d[k - 2] + d[k - 1] + 2 * l, d[i] + l + d[k - 1]}));
ans = min(ans, max({res, d[k - 2] + d[k - 1] + l, d[k - 1] + d[k - 3] + 2 * l}));
ans = min(ans, max({res, d[k - 2] + d[k - 1] + l, d[k - 2] + d[k - 3] + 2 * l}));
return ans;
}
}
