#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define FI first
#define SE second
const int MAX_N = 1e5 + 5;
///graph traverse
vector<pair<int, int>> adj[MAX_N];
///cal min longest path for each tree
bool use[MAX_N];
pair<int, int> f[MAX_N];
int Min;
///cal ans
vector<int> vec;
int Ans;
void maximize_pair(pair<int,int> &a, int v) {
if(v > a.FI) {
a.SE = a.FI;
a.FI = v;
}
else if(v > a.SE) {
a.SE = v;
}
}
void dfs1(int u, int par) {
use[u] = 1;
for(auto v : adj[u]) if(v.FI != par) {
dfs1(v.FI, u);
maximize_pair(f[u], f[v.FI].FI + v.SE);
}
}
void reroot(int u, int par) {
Min = min(Min, f[u].FI);
Ans = max(Ans, f[u].FI + f[u].SE);
for(auto v : adj[u]) if(v.FI != par) {
if(f[v.FI].FI + v.SE == f[u].FI) {
maximize_pair(f[v.FI], f[u].SE + v.SE);
}
else {
maximize_pair(f[v.FI], f[u].FI + v.SE);
}
reroot(v.FI, u);
}
}
void cal(int u) {
dfs1(u, 0);
Min = INT_MAX;
reroot(u, 0);
vec.push_back(Min);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
Ans = 0;
for(int u = 0; u < N; u++) if(!use[u]) {
cal(u);
}
if(vec.size() == 2) {
Ans = max(Ans, vec[0] + vec[1] + L);
}
else if(vec.size() > 2) {
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
Ans = max(Ans, max(vec[0] + vec[1] + L, vec[1] + vec[2] + 2 * L));
}
return Ans;
}
