#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
signed travelTime(int n, int m, int L, int A[], int B[], int T[]) {
#define int long long
vector<pair<int,int>> path[n+3];
vector<int> dist(n+3);
vector<int> d1(n+3);
vector<int> d2(n+3);
vector<int> vis(n+3);
for(int i=0;i<n;i++)dist[i]=d1[i]=d2[i]=1e18;
for(int i=0;i<m;i++){
path[A[i]].push_back({B[i],T[i]});
path[B[i]].push_back({A[i],T[i]});
}
priority_queue<int> ans;
priority_queue<int> within;
for(int i=0;i<n;i++){
if(!vis[i]){
set<int> s;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
//1st
pq.push({0,i});
dist[i]=0;
while(!pq.empty()){
auto [W,u]=pq.top();
pq.pop();
if(W>dist[u])continue;
s.insert(u);
for(auto [v,w]:path[u]){
if(dist[v]>dist[u]+w){
dist[v]=w+dist[u];
pq.push({dist[v],v});
}
}
}
//2nd
int mx=-1,d=1;
for(auto x:s){
if(dist[x]>mx){
mx=dist[x];
d=x;
}
}
pq.push({0,d});
d1[d]=0;
while(!pq.empty()){
auto [W,u]=pq.top();
pq.pop();
if(W>d1[u])continue;
for(auto [v,w]:path[u]){
if(d1[v]>d1[u]+w){
d1[v]=w+d1[u];
pq.push({d1[v],v});
}
}
}
//3rd
mx=-1,d=1;
for(auto x:s){
if(d1[x]>mx){
mx=d1[x];
d=x;
}
}
within.push(mx); //if max is within tree
pq.push({0,d});
d2[d]=0;
while(!pq.empty()){
auto [W,u]=pq.top();
pq.pop();
if(W>d2[u])continue;
for(auto [v,w]:path[u]){
if(d2[v]>d2[u]+w){
d2[v]=w+d2[u];
pq.push({d2[v],v});
}
}
}
mx=INT_MAX;
for(auto x:s){
vis[x]=true;
mx=min(mx,max(d1[x],d2[x]));
}
ans.push(mx);
for(int x : s){
dist[x] = d1[x] = d2[x] = INT_MAX;
}
}
}
if(ans.size()==1){
return ans.top();
}
if(ans.size()==2){
int k=ans.top();
ans.pop();
return max(within.top(),k+L+ans.top());
}
int k1=ans.top();
ans.pop();
int k2=ans.top();
ans.pop();
int k3=ans.top();
return max(within.top(),max(k1+k2+L,k2+k3+2*L));
#undef int
}
//#undef int
