#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int mxN = 1e5 + 100;
const int INF = 1e9;
vector<pair<int,int>> adj[mxN];
int down_dp[mxN], up_dp[mxN];
bool vis[mxN];
int cmax = 0, cost = 0;
void dfs(int u, int p){
vis[u] = 1;
// cout << u << " ";
for(auto it : adj[u]){
if(it.first ^ p){
dfs(it.first, u);
down_dp[u] = max(down_dp[u], down_dp[it.first] + it.second);
}
}
}
void reroot(int u, int p){
pair<int, int> mx1, mx2;
mx1.first = mx2.first = mx2.second = -1;
for(auto it : adj[u]){
if(it.first ^ p){
if(mx1.first == -1){
mx1.first = it.first;
mx1.second = down_dp[it.first] + it.second;
}else if(down_dp[it.first] + it.second >= mx1.second){
swap(mx1, mx2);
mx1.first = it.first;
mx1.second = down_dp[it.first] + it.second;
}else if(down_dp[it.first] + it.second > mx2.second){
mx2.first = it.first;
mx2.second = down_dp[it.first] + it.second;
}
}
}
for(auto it : adj[u]){
if(it.first ^ p){
if(it.first == mx1.first){
if(mx2.first != -1){
up_dp[it.first] = mx2.second + it.second;
}
}else if(mx1.first != 1){
up_dp[it.first] = mx1.second + it.second;
}
up_dp[it.first] = max(up_dp[it.first], up_dp[u] + it.second);
reroot(it.first, u);
}
}
cmax = min(cmax, max(up_dp[u], down_dp[u]));
cost = max({up_dp[u], down_dp[u], cost});
}
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]});
}
vector<int> tokens;
for(int i = 0; i < N; ++i){
if(!vis[i]){
cmax = INF;
// cout << "started visiting:- ";
dfs(i, -1);
reroot(i, -1);
// cout << "ended visiting\n";
tokens.push_back(cmax);
// cout << i << " " << cmax << endl;
}
}
sort(tokens.begin(), tokens.end());
// cout << "2 updp : " << up_dp[2] << " downdp: " << down_dp[2] << endl;
if(tokens.size() == 1){
return max(cost, tokens.back());
}else{
return max(cost, tokens[tokens.size() - 2] + L + tokens.back());
}
}
