#include "dreaming.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int N, M, L;
int big[100005];
bool vis[100005];
vector<pii> adj[100005];
pii best[100005];
pii best2[100005];
int p;
int ans;
int res;
void DFS(int u, int p) {
int v, w;
vis[u] = 1;
for(pii now : adj[u]) {
v = now.first, w = now.second;
if(v == p) continue;
DFS(v, u);
if(best[v].first + w > best[u].first) {
best2[u] = best[u];
best[u].first = best[v].first + w;
best[u].second = v;
}else if(best[v].first + w > best2[u].first) {
best2[u].first = best[v].first + w;
best2[u].second = v;
}
}
}
void reroot(int u, int p, int pw = 0) {
if(p != -1) {
if(best[p].second != u) {
if(best[p].first + pw >= best[u].first) {
best2[u] = best[u];
best[u].first = best[p].first + pw;
best[u].second = -1;
}else if(best[p].first + pw > best2[u].first) {
best2[u].first = best[p].first + pw;
best2[u].second = -1;
}
}else {
if(best2[p].first + pw >= best[u].first) {
best2[u] = best[u];
best[u].first = best2[p].first + pw;
best[u].second = -1;
}else if(best2[p].first + pw > best2[u].first) {
best2[u].first = best2[p].first + pw;
best2[u].second = -1;
}
}
}
ans = max(ans, best[u].first + best2[u].first);
// cout << u << ":\n";
// cout << best[u].first << " " << best[u].second << "\n";
// cout << best2[u].first << " " << best2[u].second << "\n\n";
res = min(res, best[u].first);
for(pii now : adj[u]) {
if(now.first == p) continue;
reroot(now.first, u, now.second);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
N = n, M = m, L = l;
for(int i = 0; i < N; i++) best[i] = {0, i}, best2[i] = {-1, -1};
for(int i = 0; i < M; i++) {
// cout << a[i] << " " << b[i] << " " << t[i] << "\n";
adj[a[i]].emplace_back(b[i], t[i]);
adj[b[i]].emplace_back(a[i], t[i]);
}
for(int i = 0; i < N; i++) {
if(vis[i] == 0) {
res = 0x3f3f3f3f;
DFS(i, -1);
reroot(i, -1);
big[p++] = res;
// cout << i << " " << res << "\n";
}
}
// for(int i = 0; i < p; i++) cout << big[i] << " ";
sort(big, big + p, greater<int>());
// for(int i = 0; i < p; i++) cout << big[i] << " ";
cout << "\n";
if(p > 1) ans = max(ans, big[0] + big[1] + L);
if(p > 2) ans = max(ans, big[1] + big[2] + L * 2);
return ans;
}
