#include "dreaming.h"
#include <vector>
#include <bitset>
#include <iostream>
#include <algorithm>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
#define f first
#define s second
int const N = 1e5+10;
#define endl '\n'
vector<pii> adj[N];
int max1[N];
int max2[N];
int ans[N];
pii par[N];
bitset<N> vis1;
bitset<N> vis2;
#define all(x) begin(x),end(x)
int find(int n){
if(par[n].f == n) return n;
else return par[n].f = find(par[n].f);
}
void dfs(int n,int p){
vis1[n] = 1;
//cout << n << " " << p << endl;
for(auto [k,w]:adj[n]){
if(k == p) continue;
dfs(k,n);
if(max1[k]+w > max1[n]){
max2[n] = max1[n];
max1[n] = max1[k]+w;
}
else if(max1[k]+w > max2[n]){
max2[n] = max1[k]+w;
}
}
//cout << n << " " << max1[n] << " " << max2[n] << endl;
}
void dfs2(int n,int p,int val){
vis2[n] = 1;
ans[n] = max(val,max1[n]);
for(auto [k,w]:adj[n]){
if(k == p) continue;
if(max1[k]+w == max1[n]) dfs2(k,n,max(val,max2[n])+w);
else dfs2(k,n,ans[n]+w);
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for(int i{};i < m;i++){
adj[A[i]].emplace_back(B[i],T[i]);
adj[B[i]].emplace_back(A[i],T[i]);
}
for(int i{};i < n;i++){
if(!vis1[i]) dfs(i,-1);
}
// for(int i{};i < n;i++){
// cout << max1[i] << " ";
// }
// cout << endl;
for(int i{};i < n;i++){
if(!vis2[i]) dfs2(i,-1,0);
}
// for(int i{};i < n;i++){
// cout << ans[i] << " ";
// }
// cout << endl;
int maxi = 0;
for(int i{};i < n;i++){
par[i] = {i,ans[i]};
maxi = max(maxi,ans[i]);
}
for(int i{};i < n;i++){
int para = find(A[i]);
int parb = find(B[i]);
if(para != parb){
par[parb].f = para;
par[para].s = min(par[para].s,par[parb].s);
}
}
vector<int> vc;
for(int i{};i < n;i++){
if(par[i].f == i) vc.emplace_back(par[i].s);
}
sort(all(vc),greater<int>());
if(n-m == 1) return maxi;
else if(n-m == 2) return max(maxi,vc[0]+vc[1]+L);
else return max(maxi,max(vc[0]+vc[1]+L,vc[1]+vc[2]+2*L));
}
