#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int MAXN = 1e5+10;
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
vector<pii> g[MAXN];
bool mk[MAXN];
int dist[MAXN][2];
pii dfs(int u, int p = -1) {
pii ans={0,u};
mk[u] = 1;
for (auto &[v,w] : g[u]) {
if (v == p) continue;
pii x = dfs(v,u);
x.fi+=w;
ans = max(ans, x);
}
return ans;
}
void dfs2(int u, int k, int p = -1) {
for (auto &[v,w] : g[u]) {
if (v==p) continue;
dist[v][k] = dist[u][k] + w;
dfs2(v,k,u);
}
}
int dfs3(int u, int p = -1) {
int x = max(dist[u][0], dist[u][1]);
for (auto &[v,w] : g[u]) {
if (v==p)continue;
x = min(x, dfs3(v,u));
}
return x;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
rep(i,0,M-1) {
g[A[i]].emplace_back(B[i], T[i]);
g[B[i]].emplace_back(A[i], T[i]);
}
vector<int> mxd;
int ans = 0;
rep(i,0,N-1) {
if (mk[i]) continue;
auto [_, c1] = dfs(i);
auto [d, c2] = dfs(c1);
dfs2(c1,0);
dfs2(c2,1);
ans = max(ans,d);
mxd.push_back(dfs3(i));
}
sort(all(mxd), greater<int>());
if (mxd.size() > 1) {
ans = max(ans, L+mxd[0]+mxd[1]);
}
if (mxd.size() > 2) {
ans = max(ans, 2*L + mxd[1] + mxd[2]);
}
return ans;
}
