#include "dreaming.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
vector <pair<int, int>> g[MAX+2];
vector <int> dis(MAX+2), col(MAX+2, 0), p(MAX+2, 0);
vector <int> tp;
int w, ans;
void dfs(int u, int c=-1) {
col[u] = 1;
tp.pb(u);
for (auto &i : g[u]) {
if (i.ff == c) continue;
dis[i.ff] = dis[u] + i.ss;
p[i.ff] = u;
dfs(i.ff, u);
w += i.ss;
}
}
int get(int u) {
tp.clear();
dis[u] = 0;
dfs(u);
int c = u;
for (int &i : tp) {
if (dis[c] < dis[i]) c = i;
}
tp.clear();
dis[c] = 0;
p[c] = -1;
dfs(c);
int c1 = c;
for (int &i : tp) {
if (dis[c1] < dis[i]) c1 = i;
}
vector <int> a;
int c11 = c1;
while (c1 != -1) {
a.pb(c1);
c1 = p[c1];
}
c1 = c11;
int d = dis[c1], res = c;
for (int &i : a) {
int xr = max(dis[res], d - dis[res]);
int xi = max(dis[i], d - dis[i]);
if (xi < xr) res = i;
}
ans = max(ans, dis[c1]);
return max(dis[res], d - dis[res]);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for (int i = 0; i < m; i++) {
g[A[i] + 1].pb({B[i]+1, T[i]});
g[B[i] + 1].pb({A[i]+1, T[i]});
}
vector <int> a;
for (int i = 1; i <= n; i++) {
if (col[i]) continue;
a.pb(get(i));
}
sort(all(a),greater<int>());
for (int &i : a) cerr << i << ' ';
if (a.size() == 1) ans = max(ans, a[0]);
else if (a.size() == 2) ans = max(ans, a[0] + a[1] + L);
else ans = max({ans, a[0] + a[1] + L, a[1] + a[2] + 2 * L});
return ans;
}
