#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <math.h>
#include <random>
#include <string>
#include <cstring>
#include "dreaming.h"
#include <set>
#include <vector>
#include <map>
using namespace std;
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
const int inf = 2e9;
const int N = 2e5 + 15;
int n, m, l, maxdiam, sz[N], d[N], center[N], deg[N], p[N], par[N], val[N];
vector <pii> g[N];
set <int> c, comp;
vector <int> f[N];
int used[N];
queue <int> q;
int find(int v) {
if(v == p[v])
return v;
return p[v] = find(p[v]);
}
void unio(int a, int b) {
a = find(a);
b = find(b);
if(a != b) {
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
}
int bfs(int s, int mark) {
q.push(s);
int ind = s;
used[s] = mark;
d[s] = 0;
while(!q.empty()) {
int v = q.front();
if(d[v] > d[ind])
ind = v;
q.pop();
for(pii to : g[v])
if(used[to.f] != mark) {
used[to.f] = mark;
d[to.f] = d[v] + to.se;
q.push(to.f);
}
}
return ind;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, l = L;
for(int i = 0; i < n; ++i)
p[i] = i, sz[i] = 1;
for(int i = 0; i < m; ++i) {
g[A[i]].pb(mp(B[i], T[i]));
g[B[i]].pb(mp(A[i], T[i]));
unio(A[i], B[i]);
}
for(int i = 0; i < n; ++i) {
comp.insert(find(i));
f[find(i)].pb(i);
}
for(int i : comp) {
int x = bfs(f[i].back(), 1);
int y = bfs(x, 2);
int s = d[y], f = d[y], c = y;
while(d[y] > 0) {
for(pii to : g[y])
if(d[to.f] == d[y] - to.se) {
y = to.f;
break;
}
int val = max(d[y], f - d[y]);
if(val < s) {
s = val;
c = y;
}
}
if(val[maxdiam] < s) {
val[c] = s;
maxdiam = c;
}
center[find(x)] = c;
}
for(int i : comp) {
if(find(maxdiam) == i)
continue;
g[maxdiam].pb(mp(center[i], l));
g[center[i]].pb(mp(maxdiam, l));
}
bfs(bfs(0, 1), 2);
return *max_element(d, d + n);
}
