#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const int MAXN = (int) 1e5;
static vector < pair <int, int> > g[MAXN + 1];
static int dstA[MAXN + 1], dstB[MAXN + 1];
static bool vis[MAXN + 1], on_way[MAXN + 1];
static vector <int> nodes;
void dfs(int nod, int par, int *dst) {
if(vis[nod] == 0) {
nodes.push_back(nod);
}
vis[nod] = 1;
for(auto it : g[nod]) {
if(it.first != par) {
dst[it.first] = dst[nod] + it.second;
dfs(it.first, nod, dst);
}
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
int i;
for(i = 0; i < m; i++) {
A[i]++, B[i]++;
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector <int> dst;
int ans = 0;
for(i = 1; i <= n; i++) {
if(vis[i]) continue;
nodes.clear();
dfs(i, 0, dstA);
int a = 0;
for(auto it : nodes) {
if(dstA[it] >= dstA[a]) {
a = it;
}
}
dstA[a] = 0;
dfs(a, 0, dstA);
int b = 0;
for(auto it : nodes) {
if(dstA[it] >= dstA[b]) {
b = it;
}
}
dfs(b, 0, dstB);
ans = max(ans, dstA[b]);
int cur_dst = INF;
for(auto it : nodes) {
if(cur_dst >= max(dstA[it], dstB[it])) {
cur_dst = max(dstA[it], dstB[it]);
}
}
dst.push_back(cur_dst);
}
sort(dst.rbegin(), dst.rend());
if(dst.size() > 1) {
ans = max(ans, dst[0] + dst[1] + l);
}
return ans;
}
