#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<array<int, 2>> adj[N], nadj[N];
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i = 0; i < M; ++i)
{
int u = A[i], v = B[i], w = T[i];
++u, ++v;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
nadj[u].push_back({v, w});
nadj[v].push_back({u, w});
}
vector<array<int, 2>> add;
vector<bool> used(N + 1, false);
for (int i = 1; i <= N; ++i)
{
if (used[i]) continue;
map<int, int> mp;
function<void(int)> dfs1 = [&](int u)
{
used[u] = true;
for (auto &[v, w] : adj[u])
{
if (used[v]) continue;
mp[v] = mp[u] + w;
dfs1(v);
}
};
dfs1(i);
int node = 0;
for (auto &[u, d] : mp)
{
if (d > mp[node]) node = u;
}
for (auto &[u, d] : mp) used[u] = false;
mp[node] = 0;
dfs1(node);
int vertex = 0;
for (auto &[u, d] : mp)
{
if (d > mp[vertex]) vertex = u;
}
for (auto &[u, d] : mp) used[u] = false;
map<int, int> mp1;
function<void(int)> dfs2 = [&](int u)
{
used[u] = true;
for (auto &[v, w] : adj[u])
{
if (used[v]) continue;
mp1[v] = mp1[u] + w;
dfs2(v);
}
};
dfs2(vertex);
// cout << vertex << '\n';
// for (auto &[u, d] : mp1) cout << u << ' ' << d << '\n';
// cout << '\n';
// continue;
map<int, int> mx;
for (auto &[u, d] : mp1)
{
mx[u] = max(d, mp[u]);
}
// for (auto &[u, d] : mx) cout << u << ' ' << d << '\n';
// cout << '\n';
// continue;
int mn = 0;
mx[mn] = 1e9;
for (auto &[u, d] : mx)
{
if (d <= mx[mn]) mn = u;
// cout << u << ' ' << mx[u] << ' ';
}
// cout << '\n';
if (adj[i].empty()) mn = i;
add.push_back({mn, mx[vertex]});
}
sort (add.begin(), add.end(), [&](auto i, auto j)
{
return i[1] > j[1];
});
int u = add[0][0];
for (int i = 1; i < size(add); ++i)
{
int v = add[i][0];
nadj[u].push_back({v, L});
nadj[v].push_back({u, L});
}
for (int i = 1; i <= N; ++i) used[i] = false;
vector<int> d(N + 1, 0);
function<void(int)> dfs = [&](int u)
{
used[u] = true;
for (auto &[v, w] : nadj[u])
{
if (used[v]) continue;
d[v] = d[u] + w;
dfs(v);
}
};
dfs(1);
int node = 0;
for (int i = 1; i <= N; ++i)
{
if (d[i] >= d[node]) node = i;
}
for (int i = 1; i <= N; ++i) used[i] = false;
d[node] = 0;
dfs(node);
int vertex = 0;
for (int i = 1; i <= N; ++i)
{
if (d[i] >= d[vertex]) vertex = i;
}
for (int i = 1; i <= N; ++i) used[i] = false;
vector<int> d1(N + 1, 0);
function<void(int)> dfs2 = [&](int u)
{
used[u] = true;
for (auto &[v, w] : nadj[u])
{
if (used[v]) continue;
d1[v] = d1[u] + w;
dfs2(v);
}
};
dfs2(vertex);
return d1[node];
}
