#include "dreaming.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int ty, st, md, dist[100005][2];
bool vis[100005];
vector<int> vec;
vector<ii> adj[100005];
void dfs(int n, int e = -1, int d = 0) {
if (ty != -1) dist[n][ty] = d;
else vec.pb(n);
if (d > md) {
md = d;
st = n;
}
for (auto u : adj[n])
if (u.first != e)
dfs(u.first, n, d + u.second);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
adj[A[i]].eb(B[i], T[i]);
adj[B[i]].eb(A[i], T[i]);
}
vector<ii> proc;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
vec.clear();
md = -1;
ty = -1;
dfs(i);
md = -1;
ty = 0;
dfs(st);
ty = 1;
dfs(st);
int curm = INT_MAX, cent = -1;
for (int j : vec) {
if (max(dist[j][0], dist[j][1]) < curm) {
curm = max(dist[j][0], dist[j][1]);
cent = j;
}
vis[j] = 1;
}
proc.eb(curm, cent);
}
}
sort(proc.begin(), proc.end(), greater<ii>());
for (int i = 1; i < proc.size(); i++) {
adj[proc[0].second].eb(proc[i].second, L);
adj[proc[i].second].eb(proc[0].second, L);
}
md = ty = -1;
dfs(0);
dfs(st);
return md;
}
