#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define cmax(a, b) a=max(a, b)
#define cmin(a, b) a=min(a, b)
#define sz(x) (int)x.size()
#define fi first
#define se second
using namespace std;
int n, m, k, cur, mx=0;
vector<vector<pair<int, int>>> adj;
vector<int> dist;
vector<bool> vis;
int dfs(int u, int p=-1) {
dist[u]=0;
for (auto [v, w]: adj[u]) if (v!=p) {
cmax(dist[u], dfs(v, u)+w);
}
return dist[u];
}
void dfs2(int u, int p=-1, int act=0) {
if (dist[u]<cur) cur=dist[u];
cmax(mx, dist[u]);
vis[u]=1;
vector<pair<int, int>> children; children.pb({act, -1});
for (auto [v, w]: adj[u]) if (v!=p) {
children.pb({dist[v]+w, v});
}
sort(rall(children));
for (auto [v, w]: adj[u]) if (v!=p) {
int best=children[0].fi; if (children[0].se==v) best=children[1].fi;
cmax(dist[v], best+w);
dfs2(v, u, best+w);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N, m=M, k=L;
adj.resize(n), dist.resize(n, -1);
for (int i=0; i<m; i++) {
adj[A[i]].pb({B[i], T[i]});
adj[B[i]].pb({A[i], T[i]});
}
for (int i=0; i<n; i++) {
if (dist[i]==-1) dfs(i);
}
vis.resize(n);
vector<int> vec;
for (int i=0; i<n; i++) {
if (!vis[i]) {
cur=dist[i];
dfs2(i);
vec.pb(cur);
}
}
sort(rall(vec));
for (int i=1; i<sz(vec); i++) {
int du=vec[i-1], dv=vec[i];
cmax(mx, du+k+dv);
cmax(vec[i-1], du+k), cmax(vec[i], dv+k);
if (vec[i-1]<vec[i]) swap(vec[i], vec[i-1]);
}
return mx;
}
