#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 1e9+7;
const int NMAX = 1e5+10;
vector<P> g[NMAX];
int max_dis, endpoint, ok = 0;
int dp[NMAX], vis[NMAX];
vector<int> members, W;
void dfs(int node, int par, int dis) { // finding one endpoint of the diametr
vis[node] = 1;
if (dis > max_dis)
max_dis = dis,
endpoint = node;
for (auto [v, w]: g[node])
if (v != par)dfs(v, node, dis+w);
}
void calc_dp(int node, int par, int dis) { // dp[nd] = max(dis(nd, a), dis(nd, b)), where a and b is endpoints of the diametr
dp[node] = max(dp[node], dis);
if(ok)members.push_back(node);
for (auto [v, w]: g[node])
if (v != par)calc_dp(v, node, dis+w);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
rep(i, 0, M)
g[A[i]].push_back(P(B[i], T[i])),
g[B[i]].push_back(P(A[i], T[i]));
int res = 0;
int cnt = 0;
rep(i, 0, N) {
if (vis[i])continue;
cnt += 1;
max_dis = 0, endpoint = i;
dfs(i, i, 0);
int a = endpoint; max_dis = 0;
dfs(a, a, 0); res = max(res, max_dis);
int b = endpoint; ok = 1;
calc_dp(a, a, 0); ok = 0;
calc_dp(b, b, 0);
int mn = 1e9;
for (auto v: members)mn = min(mn, dp[v]);
W.push_back(mn); members.clear();
}
sort(W.rbegin(), W.rend());
if (sz(W) >= 2)res = max(res, W[0]+W[1]+L);
if (sz(W) >= 3)res = max(res, W[1]+W[2]+2*L);
return res;
}
