#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAX = 1e5 + 10;
int ans;
vector <pair <int, int>> adj[MAX];
pair <int, int> ma[MAX][2];
bool visited[MAX];
template <typename T>
void upd(T *ma, T x, int n) {
for(int i = 0; i < n; i++) {
if(ma[i] < x) {
swap(ma[i], x);
}
}
}
void dfs(int u) {
for(auto [v, w] : adj[u]) {
if(visited[v] == true) {
continue;
}
visited[v] = true;
dfs(v);
upd(ma[u], make_pair(ma[v][0].first + w, v), 2);
}
ans = max(ans, ma[u][0].first + ma[u][1].first);
}
int dfs2(int u, int pw) {
int res = max(ma[u][0].first, pw);
for(auto [v, w] : adj[u]) {
if(visited[v] == true) {
continue;
}
visited[v] = true;
int nw = pw;
if(ma[u][0].second == v) {
nw = max(nw, ma[u][1].first);
}
else {
nw = max(nw, ma[u][0].first);
}
res = min(res, dfs2(v, nw + w));
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++) {
A[i]++, B[i]++;
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
for(int i = 1; i <= N; i++) {
ma[i][0] = make_pair(0, -1);
ma[i][1] = make_pair(0, -1);
}
for(int i = 1; i <= N; i++) {
if(visited[i] == false) {
visited[i] = true;
dfs(i);
}
}
for(int i = 1; i <= N; i++) {
visited[i] = false;
}
vector <int> max_dist;
for(int i = 1; i <= N; i++) {
if(visited[i] == false) {
visited[i] = true;
max_dist.push_back(dfs2(i, 0));
}
}
sort(max_dist.rbegin(), max_dist.rend());
if(max_dist.size() > 1) {
ans = max(ans, max_dist[0] + max_dist[1] + L);
}
if(max_dist.size() > 2) {
ans = max(ans, max_dist[1] + max_dist[2] + 2 * L);
}
return ans;
}
