#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<pair<int,long long>>> Graph(N);
for(int i=0; i<M; i++){
int u = A[i],v = B[i],w = T[i];
Graph.at(u).push_back({v,w});
Graph.at(v).push_back({u,w});
}
vector<bool> already(N);
vector<int> par(N,-1);
vector<vector<long long>> kid(N);
vector<long long> dist;
long long answer = 0;
for(int i=0; i<N; i++) if(already.at(i) == false){
{
auto dfs = [&](auto dfs,int pos,int back) -> long long {
already.at(pos) = true;
kid.at(pos).resize(Graph.at(pos).size());
long long ret = 0;
for(int i=0; i<Graph.at(pos).size(); i++){
auto [to,w] = Graph.at(pos).at(i);
if(to == back) par.at(pos) = i;
else{
long long k = dfs(dfs,to,pos)+w;
kid.at(pos).at(i) = k;
ret = max(ret,k);
}
}
return ret;
};
dfs(dfs,i,-1);
}
{
long long now = numeric_limits<long long>::max();
auto dfs = [&](auto dfs,int pos,int back,long long take) -> void {
if(back != -1) kid.at(pos).at(par.at(pos)) = take;
auto L = kid.at(pos),R = L;
if(L.size() == 0){now = 0; return;}
for(int i=1; i<L.size(); i++) L.at(i) = max(L.at(i),L.at(i-1));
for(int i=(int)R.size()-2; i>=0; i--) R.at(i) = max(R.at(i),R.at(i+1));
now = min(now,L.back());
answer = max(answer,L.back());
for(int i=0; i<Graph.at(pos).size(); i++){
auto [to,w] = Graph.at(pos).at(i);
if(to == back) continue;
long long give = 0;
if(i) give = L.at(i-1);
if(i+1 < Graph.at(pos).size()) give = max(give,R.at(i+1));
give += w;
dfs(dfs,to,pos,give);
}
};
dfs(dfs,i,-1,-1);
dist.push_back(now);
}
}
sort(dist.rbegin(),dist.rend());
if(M == N-1) return max(answer,dist.at(0));
else if(M == N-2) return max(answer,dist.at(0)+dist.at(1)+L);
else return max(answer,max(dist.at(0)+dist.at(1)+L,dist.at(1)+dist.at(2)+L+L));
}
