#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
#define fi first
#define se second
vector<int> Tree;
int d[N];
bool used[N];
int pa[N];
vector<pair<int, int>> g[N];
void dfs (int u, int p) {
Tree.push_back(u);
used[u] = 1;
pa[u] = p;
for (auto& e : g[u]) {
int v = e.fi;
int w = e.se;
if (v != p) {
d[v] = d[u] + w;
dfs(v, u);
}
}
}
// int travelTime (int n, int m, int L, vector<int> A, vector<int> B, vector<int> T) {
int travelTime (int n, int m, int L, int A[], int B[], int T[]) {
for (int i = 0; i < m; i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
int longest = 0;
int mxrad = 0;
int root = -1;
vector<int> center;
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs(i, -1);
int v = i;
for (auto& j : Tree) if (d[j] > d[v]) v = j;
Tree.clear();
d[v] = 0;
dfs(v, -1);
for (auto &j : Tree) if (d[j] > d[v]) v = j;
int u = v;
int x = v;
while (u != -1) {
if (abs(2 * d[u] - d[v]) < abs(2 * d[x] - d[v])) {
x = u;
}
u = pa[u];
}
if (mxrad < max(d[x], d[v] - d[x])) {
mxrad = max(d[x], d[v] - d[x]);
root = x;
}
center.push_back(x);
longest = max(longest, d[v]);
Tree.clear();
}
}
for (int i = 0; i < center.size(); i++) {
if (center[i] != root) {
g[root].push_back({center[i], L});
g[center[i]].push_back({root, L});
}
}
dfs(0, -1);
int v = 0;
for (auto &j : Tree) if (d[j] > d[v]) v = j;
d[v] = 0;
dfs(v, -1);
for (auto &j : Tree) if (d[j] > d[v]) v = j;
longest = max(longest, d[v]);
return longest;
}
// signed main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//
// int n, m, L;
// cin >> n >> m >> L;
// vector<int> A(m), B(m), T(m);
// for (int i = 0; i < m; i++) cin >> A[i] >> B[i] >> T[i];
//
// cout << travelTime(n,m,L,A,B,T);
//
// return 0;
// }
