#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > adj;
vector<long long> res;
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
adj.resize(N);
res.resize(N);
for(int i = 0; i < M; i++){
adj[A[i]].push_back(make_pair(B[i], T[i]));
adj[B[i]].push_back(make_pair(A[i], T[i]));
}
vector<int> distances(N, 1e9);
vector<int> distancesA(N, 1e9);
vector<int> distancesB(N, 1e9);
vector<int> thing;
int diameter = 0;
vector<bool> visited(N);
for(int i = 0; i < N; i++){
if(!visited[i]){
queue<int> q;
q.push(i);
distances[i] = 0;
int a = i;
int mxDist = 0;
vector<int> comp;
while(!q.empty()){
int u = q.front();
q.pop();
visited[u] = true;
comp.push_back(u);
if(distances[u] > mxDist){
mxDist = distances[u];
a = u;
}
for(pair<int, int> x : adj[u]){
if(distances[x.first] > distances[u] + x.second){
q.push(x.first);
distances[x.first] = distances[u] + x.second;
}
}
}
q.push(a);
distancesA[a] = 0;
int b = a;
int mxDist2 = 0;
while(!q.empty()){
int u = q.front();
q.pop();
if(distancesA[u] > mxDist2){
mxDist2 = distancesA[u];
b = u;
}
for(pair<int, int> x : adj[u]){
if(distancesA[x.first] > distancesA[u] + x.second){
q.push(x.first);
distancesA[x.first] = distancesA[u] + x.second;
}
}
}
diameter = max(diameter, mxDist2);
q.push(b);
distancesB[b] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
for(pair<int, int> x : adj[u]){
if(distancesB[x.first] > distancesB[u] + x.second){
q.push(x.first);
distancesB[x.first] = distancesB[u] + x.second;
}
}
}
int val = 1e9;
for(int x : comp){
val = min(val, max(distancesA[x], distancesB[x]));
}
thing.push_back(val);
}
}
sort(thing.begin(), thing.end());
reverse(thing.begin(), thing.end());
if((int)thing.size() > 1){
int stuff1 = thing[0] + thing[1] + L;
if((int)thing.size() == 2){
return max(stuff1, diameter);
}
else{
return max(max(stuff1, thing[1] + thing[2] + 2 * L), diameter);
}
}
else{
return diameter;
}
}
