#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<vector<int>>> graph(N);
for (int i = 0; i < M; i++) {
int x,y,z; x = A[i]; y = B[i]; z = T[i];
graph[x].push_back({y,z});
graph[y].push_back({x,z});
}
vector<int> radius;
vector<int> diameter;
bool vis1[N] = {}, vis2[N] = {};
int vis3[N] = {};
for (int i = 0; i < N; i++) {
if (!vis1[i]) {
queue<pair<int, int>> bfs;
bfs.push(make_pair(i, 0));
vis1[i] = true;
int start = 0, weight = 0;
while (!bfs.empty()) {
int x = bfs.front().first;
int y = bfs.front().second;
bfs.pop();
if (y > weight) {
start = x;
weight = y;
}
for (int j = 0; j < graph[x].size(); j++) {
if (vis1[graph[x][j][0]] == false) {
bfs.push(make_pair(graph[x][j][0], graph[x][j][1]+y));
vis1[graph[x][j][0]] = true;
}
}
}
bfs.push(make_pair(start, 0));
vis2[start] = true;
int end = 0; weight = 0;
while (!bfs.empty()) {
int x = bfs.front().first;
int y = bfs.front().second;
bfs.pop();
if (y > weight) {
end = x;
weight = y;
}
for (int j = 0; j < graph[x].size(); j++) {
if (vis2[graph[x][j][0]] == false) {
bfs.push(make_pair(graph[x][j][0], graph[x][j][1]+y));
vis2[graph[x][j][0]] = true;
}
}
}
diameter.push_back(weight);
int rad = weight;
stack<int> dfs;
dfs.push(start);
while (!dfs.empty()) {
int x = dfs.top();
if (x == end) {
int curr = 0;
dfs.pop();
while (!dfs.empty()) {
int y = dfs.top();
dfs.pop();
for (int j = 0; j < graph[x].size(); j++) {
if (graph[x][j][0] == y) {
curr += graph[x][j][1];
rad = min(rad,max(curr,weight-curr));
break;
}
}
x = y;
}
} else if (vis3[x] == graph[x].size()) {
dfs.pop();
} else {
dfs.push(graph[x][vis3[x]][0]);
vis3[x]++;
}
}
radius.push_back(rad);
}
}
sort(radius.begin(), radius.end(), greater<int>());
sort(diameter.begin(),diameter.end(), greater<int>());
if (radius.size() == 1) {
return (diameter[0]);
} else if (radius.size() == 2) {
return max({radius[0]+radius[1]+L, diameter[0]});
} else {
return max({radius[0]+radius[1]+L, radius[1]+radius[2]+L+L, diameter[0]});
}
}
