#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
vector <pair<int, int> > g[N];
vector <int> pref[N];
bool used[N];
int dp[N][2], n;
void dfs1(int v, int p){
used[v] = 1;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first, len = g[v][i].second;
if (to == p)
continue;
dfs1(to, v);
dp[v][0] = max(dp[v][0], dp[to][0] + len);
}
}
int mn, pos = 0;
void dfs2(int v, int p){
int mx = 0;
for (int i = g[v].size()-1; i >= 0; i--){
int to = g[v][i].first, len = g[v][i].second;
if (to == p)
continue;
mx = max(mx, dp[to][0]+len);
pref[v].push_back(mx);
}
mx = max(mx, dp[p][1]);
if (mx < mn){
mn = mx;
pos = v;
}
mx = dp[p][1];
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first, len = g[v][i].second;
if (to == p)
continue;
pref[v].pop_back();
int mx2 = 0;
if (!pref[v].empty())
mx2 = pref[v].back();
dp[v][1] = max(mx, mx2)+len;
dfs2(to, v);
mx = max(mx, dp[to][0]+len);
}
}
void dfs3(int v, int p, ll curLen){
if (curLen > mn){
mn = curLen;
pos = v;
}
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first, len = g[v][i].second;
if (to == p)
continue;
dfs3(to, v, curLen+len);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
n = N;
for (int i = 1; i <= M; i++){
int u = A[i-1]+1, v = B[i-1]+1, c = T[i-1];
g[u].push_back({v, c});
g[v].push_back({u, c});
}
vector <pair<int, int> > vec;
for (int i = 1; i <= n; i++){
if (used[i])
continue;
dfs1(i, 0);
mn = 1e9+7;
pos = 0;
dfs2(i, 0);
vec.push_back({mn, pos});
}
sort(vec.rbegin(), vec.rend());
int u = vec[0].second;
for (int i = 1; i < vec.size(); i++){
int v = vec[i].second;
g[u].push_back({v, L});
g[v].push_back({u, L});
}
mn = -1;
dfs3(1, 0, 0);
mn = -1;
dfs3(pos, 0, 0);
return mn;
}
