#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#endif
#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp <<' '<<
#define F(i, s, n) for(int i = s; i < (int) n; i++)
#define pb push_back
#define fi first
#define se second
const int N = 1e5+5;
const int inf = 1e18;
vpi adj[N];
vvi trees;
bool vis1[N];
int dep1[N], dep2[N];
void get_tree(int node, int par, vector<int> *list) {
vis1[node] = 1;
list->pb(node);
for(auto &go : adj[node]) if(go.fi != par) get_tree(go.fi, node, list);
}
int dep_dfs1(int node, int par, int dep = 0) {
dep1[node] = dep;
int ans = node;
for(auto &go : adj[node]) if(go.fi != par) {
int chans = dep_dfs1(go.fi, node, dep + go.se);
if(dep1[chans] > dep1[ans]) ans = chans;
}
return ans;
}
int dep_dfs2(int node, int par, int dep = 0) {
dep2[node] = dep;
int ans = node;
for(auto &go : adj[node]) if(go.fi != par) {
int chans = dep_dfs2(go.fi, node, dep + go.se);
if(dep2[chans] > dep2[ans]) ans = chans;
}
return ans;
}
int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) {
F(i, 0, M) {
adj[A[i]].pb({B[i], T[i]});
adj[B[i]].pb({A[i], T[i]});
}
F(i, 0, N) {
if(vis1[i]) continue;
trees.pb({});
get_tree(i, i, &trees.back());
}
vi tree_lengths;
int ans_from_inner_tree = 0;
for(vector<int> &tree : trees) {
int diameter1 = dep_dfs1(tree[0], -1);
int diameter2 = dep_dfs2(diameter1, -1);
dep_dfs1(diameter2, -1);
int bestLeader = inf;
for(int node : tree) {
bestLeader = min(bestLeader, max(dep1[node], dep2[node]));
}
ans_from_inner_tree = max(ans_from_inner_tree, dep1[diameter1]);
tree_lengths.pb(bestLeader);
}
sort(tree_lengths.begin(), tree_lengths.end(), greater<int>());
if(trees.size() == 1) {
return ans_from_inner_tree;
} else if(trees.size() == 2) {
return max(ans_from_inner_tree, tree_lengths[0] + tree_lengths[1] + L);
} else {
return max({ans_from_inner_tree, tree_lengths[0] + tree_lengths[1] + L, tree_lengths[0] + tree_lengths[2] + L * 2});
}
return 31837837; // let LEBLEBIE do its magic ♦
}
