#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, INF = 1e9;
int n, m, l;
vector<pair<int,int>> adj[maxn];
int dist[maxn];
vector<int> cur;
void dfs(int u) {
cur.push_back(u);
for (auto [v, w]:adj[u]) if (dist[v] == -1) {
dist[v] = dist[u] + w;
dfs(v);
}
}
int finish;
vector<int> track;
bool done;
void dfs2(int u) {
if (!done) track.push_back(u);
if (u==finish) done = true;
for (auto [v, w]:adj[u]) if (dist[v] == -1) {
dist[v] = dist[u] + w;
dfs2(v);
}
if (!done) track.pop_back();
}
int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) {
n = N, m = M, l = L;
for (int i=0;i<m;i++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for (int i=0;i<n;i++) dist[i] = -1;
int32_t ans1 = 0;
vector<int> vals;
for (int i=0;i<n;i++) if (dist[i] == -1) {
cur.clear();
dist[i] = 0;
dfs(i);
int start = i;
for (int j:cur) if (dist[j] > dist[start]) start = j;
for (int j:cur) dist[j] = -1;
cur.clear();
dist[start] = 0;
dfs(start);
finish = start;
for (int j:cur) if (dist[j] > dist[finish]) finish = j;
ans1 = max(dist[finish], ans1);
for (int j:cur) dist[j] = -1;
dist[start] = 0, done = false;
track.clear();
dfs2(start);
int cost = INF;
for (int j:track) cost = min(max(dist[finish]-dist[j], dist[j]), cost);
vals.push_back(cost);
}
sort(vals.rbegin(), vals.rend());
int ans2 = 0, ans3 = 0;
if (vals.size() >= 2) ans2 = l + vals[0] + vals[1];
if (vals.size() >= 3) ans3 = l + l + vals[1] + vals[2];
return max({ans1, ans2, ans3});
}
