#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = (int) 3e5 + 5;
ll mes[MAXN], der[MAXN], asa[MAXN];
vector<pii> adj[MAXN];
vector<int> comps;
bool done[MAXN];
ll mn = 0;
void dfs1(int v, int par){
for(pii u: adj[v]){
if(u.ff != par){
der[u.ff] = der[v] + u.ss;
dfs1(u.ff, v);
asa[v] = max(asa[v], asa[u.ff] + u.ss);
}
}
}
int dfs(int v, int par, ll upD){
done[v] = 1;
mes[v] = max(upD, asa[v]);
int mx = v;
multiset<int> st;
st.insert(upD);
for(pii u: adj[v]){
if(u.ff != par){
st.insert(asa[u.ff] + u.ss);
}
}
if(st.size() == 1){
mn = max(mn,(ll) *st.rbegin());
}else if(st.size() > 1){
mn = max(mn, (ll)(*st.rbegin()) + (*next(st.rbegin())));
}
for(pii u: adj[v]){
if(u.ff != par){
st.erase(st.lower_bound(asa[u.ff] + u.ss));
dfs(u.ff, v, (*st.rbegin()) + u.ss);
st.insert(asa[u.ff] + u.ss);
if(mes[u.ff] < mes[mx]) mx = u.ff;
}
}
return mx;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for(int i = 0; i < N; i++){
if(!done[i]){
dfs1(i, -1);
comps.push_back(dfs(i, -1, 0));
}
//cerr<<i<<": "<<mes[i]<<endl;
}
sort(comps.begin(), comps.end(), [](int a, int b){
return mes[a] > mes[b];
});
if(comps.size() == 1){
return max(mn, mes[comps[0]]);
}else if(comps.size() == 2){
return max(mn, L + mes[comps[0]] + mes[comps[1]]);
}else{
return max(mn,max(2*L + mes[comps[1]] + mes[comps[2]], L + mes[comps[0]] + mes[comps[1]]));
}
}
