#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> graph;
vector<vector<pair<int, int>>> dis;
vector<int> vis;
vector<int> sp;
int dfs(int node, pair<int, int> prev) {
vis[node] = 1;
for (auto edge : graph[node]) {
if (edge.first != prev.first) {
pair<int, int> check = {edge.second + dfs(edge.first, {node, edge.second}), edge.first};
if (check > dis[node][0]) {
swap(check, dis[node][0]);
}
if (check > dis[node][1]) {
swap(check, dis[node][1]);
}
}
}
return dis[node][0].first;
}
int dfs1(int node, pair<int, int> prev) {
if (prev.first != -1) {
int val = 0;
int par = prev.first;
if (dis[par][0].second != node) {
val = dis[par][0].first + prev.second;
} else {
val = dis[par][1].first + prev.second;
}
pair<int, int> check = {val, par};
if (check > dis[node][0]) {
swap(check, dis[node][0]);
}
if (check > dis[node][1]) {
swap(check, dis[node][1]);
}
}
int mn = dis[node][0].first;
for (auto edge : graph[node]) {
if (edge.first != prev.first) {
mn = min(mn, dfs1(edge.first, {node, edge.second}));
}
}
return mn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
graph.resize(N);
vis.resize(N);
dis.resize(N, vector<pair<int, int>>(2, {0, -1}));
for (int i = 0; i < M; i++) {
graph[A[i]].push_back({B[i], T[i]});
graph[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < N; i++) {
if (!vis[i]) {
dfs(i, {-1, -1});
sp.push_back(dfs1(i, {-1, -1}));
}
}
sort(sp.begin(), sp.end(), greater<int>());
if (sp.size() == 1) {
return sp[0];
} else if (sp.size() == 2) {
return sp[0] + sp[1] + L;
} else {
return max(sp[0] + sp[1] + L, sp[1] + sp[2] + 2 * L);
}
}
