#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int LIM = 1e5 + 5;
vector <pair <int, int>> adj[LIM];
int dist[LIM];
void add_edge(int u, int v, int w) {
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
// cerr << u << ' ' << v << ' ' << w << '\n';
}
void dfs(int u, int p = -1) {
for (auto [v, w]: adj[u]) if (v != p) {
dist[v] = dist[u] + w;
dfs(v, u);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int root = -1, v = -1, ma = 0;
vector <bool> alone(N, true);
for (int i = 0; i < M; i++) {
if (T[i] > ma) root = A[i], v = B[i], ma = T[i];
alone[A[i]] = alone[B[i]] = false;
}
for (int i = 0; i < M; i++) {
add_edge(A[i], B[i], T[i]);
}
for (int i = 0; i < N; i++) {
if (alone[i]) add_edge(root, i, L);
}
for (int i = 0; i < M; i++) {
if (A[i] != root && B[i] != root)
add_edge(root, A[i], L);
}
dfs(root); int leaf = -1, maDis = 0;
for (int i = 0; i < N; i++)
if (maDis < dist[i]) {
maDis = dist[i];
leaf = i;
}
dist[leaf] = 0; dfs(leaf);
return *max_element(dist, dist + N);
}
