#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 100010
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll nw, w, vis[maxn], dist[maxn];
array<ll, 2> o;
vector<ll> v;
vector<array<ll, 2>> adj[maxn];
void dfs(ll ty, ll s) {
// cout << "dfs" _ ty _ s << nl;
vis[s] = ty;
for (auto [u, w] : adj[s]) {
if (vis[u] == ty) continue;
if (ty == 3) o = min(o, {max(dist[u], dist[s] + w), u});
else o = max(o, {dist[s] + w, u});
dist[u] = dist[s] + w;
// cout << "o =" _ o[0] _ o[1] << nl;
dfs(ty, u);
}
}
ll diam(ll s) {
ll i, a, b;
o = {0, s}; dist[s] = 0; dfs(1, s); a = o[1];
o = {0, a}; dist[a] = 0; dfs(2, a); b = o[1];
res = max(res, o[0]);
dist[b] = 0; dfs(3, b); return o[0];
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N; m = M; nw = L;
for (i = 1; i <= n; i++) {
a = A[i - 1] + 1; b = B[i - 1] + 1; w = T[i - 1];
adj[a].pb({b, w}); adj[b].pb({a, w});
}
for (i = 1; i <= n; i++) {
if (vis[i] != 0) continue;
v.pb(diam(i));
}
/* for (auto u : v) cout << u << ' ';
cout << nl; */
sort(v.begin(), v.end()); reverse(v.begin(), v.end());
if (m <= n - 2) res = max(res, v[0] + v[1] + nw);
if (m <= n - 3) res = max(res, v[1] + v[2] + 2 * nw);
return res;
}
