#include <bits/stdc++.h>
#include "dreaming.h"
#define ll int
#define in insert
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int sz = 2e5+5;
ll w, res;
vector<array<ll, 2>> adj[sz], dp(sz), leaf(sz);
bool used[sz];
ll node, R;
vl path;
void dfs1(ll v, ll p){
//cout << v << endl;
dp[v] = {0, 0};
leaf[v] = {v, v};
used[v] = 1;
for(array<ll, 2> e: adj[v]){
if(!used[e[0]]){
dfs1(e[0], v);
if((dp[e[0]][0] + e[1]) > dp[v][0]){
dp[v][1] = dp[v][0];
leaf[v][1] = leaf[v][0];
dp[v][0] = dp[e[0]][0] + e[1];
leaf[v][0] = leaf[e[0]][0];
}
else if((dp[e[0]][0] + e[1]) > dp[v][1]){
dp[v][1] = dp[e[0]][0] + e[1];
leaf[v][1] = leaf[e[0]][0];
}
}
}
if((dp[v][0] + dp[v][1]) > res){
node = v;
res = dp[v][0] + dp[v][1];
}
}
void getpath(ll v, ll p, ll target){
for(array<ll, 2> e: adj[v]){
if(e[0] != p){
if(dp[e[0]][0] + e[1] == target){
path.pb(e[1]);
getpath(e[0], v, target - e[1]);
return ;
}
}
}
}
ll GetR(ll v){
res = -1;
dfs1(v, 0);
//cout << endl << res << endl;
ll l1 = leaf[node][0];
ll l2 = leaf[node][1];
ll bar = res / 2;
path.clear();
getpath(node, 0, dp[node][0]);
reverse(all(path));
getpath(node, 0, dp[node][1]);
ll ret = res, cur = 0;
R = max(R, res);
for(auto x: path){
cur += x;
if(cur > bar){
ret = min(ret, cur);
}
else{
ret = min(ret, (res - cur));
}
}
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
ll n = N, m = M, i, j, k;
w = L;
for(i = 0; i < m; i++){
adj[A[i] + 1].pb({B[i] + 1, T[i]});
adj[B[i] + 1].pb({A[i] + 1, T[i]});
}
vl longest;
for(i = 1; i <= n; i++){
if(!used[i]){
//cout << i << endl;
longest.pb(GetR(i));
}
}
sort(longest.rbegin(), longest.rend());
if(longest.size() == 1){
return R;
}
else if(longest.size() == 2){
return max(R, longest[0] + longest[1] + w);
}
else{
//cout << R << ' ' << longest[0] + longest[1] + w << ' ' << longest[1] + longest[2] + 2*w << endl;
return max({R, (longest[0] + longest[1] + w), (longest[1] + longest[2] + 2*w)});
}
}
/*int main(){
ll n = 12, m = 8, L = 2;
ll a[8] = {0,8,2,5,5,1,1,10};
ll b[8] = {8,2,7,11,1,3,9,6};
ll t[8] = {4,2,4,3,7,1,5,3};
cout << travelTime(n, m, L, a, b, t);
}*/
/*
*/
