#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 200001;
struct Graph {
vector<vector<pair<int, int>>> g;
vector<int> max_dist[2];
int x, cnt;
Graph() {
g.resize(N);
max_dist[0].resize(N);
max_dist[1].resize(N);
x = cnt = 0;
}
void add(int a, int b, int w) {
x = a;
g[a].push_back({b, w});
g[b].push_back({a, w});
cnt++;
}
void update(int node, int offer) {
if (offer > max_dist[0][node]) {
max_dist[1][node] = max_dist[0][node];
max_dist[0][node] = offer;
} else if (offer > max_dist[1][node]) {
max_dist[1][node] = offer;
}
}
void dfs1(int node, int parent) {
for (auto [child, w] : g[node]) {
if (child == parent) continue;
dfs1(child, node);
update(node, max_dist[0][child] + w);
}
}
void dfs2(int node, int parent) {
for (auto [child, w] : g[node]) {
if (child == parent) continue;
if (max_dist[0][node] == max_dist[0][child] + w) {
update(child, max_dist[1][node] + w);
} else {
update(child, max_dist[0][node] + w);
}
dfs2(child, node);
}
}
int findmin() {
dfs1(x, -1);
dfs2(x, -1);
int mn = 1e9, id = -1;
for (int i = 0; i < N; i++) {
int val = max_dist[0][i];
if (val != 0 && val < mn) {
mn = val;
id = i;
}
}
return id;
}
void clear() {
g.assign(N, vector<pair<int, int>>());
max_dist[0].assign(N, 0);
max_dist[1].assign(N, 0);
x = cnt = 0;
}
};
vector<pair<int, int>> adj[N];
Graph tmp;
bool vis[N];
void dfs(int u) {
vis[u] = 1;
for (auto [v, w] : adj[u]) {
if (!vis[v]) {
tmp.add(u, v, w);
dfs(v);
}
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
Graph res;
vector<bool> is(n);
for (int i = 0; i < m; i++) {
int u = a[i], v = b[i], w = t[i];
is[u] = is[v] = 1;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
res.add(u, v, w);
}
vector<int> v;
for (int i = 0; i < n; i++) {
if (!is[i]) v.push_back(i);
}
for (int i = 0; i < n; i++) {
if (!vis[i] && is[i]) {
tmp.clear();
dfs(i);
v.push_back(tmp.findmin());
}
}
for (int i = 1; i < v.size(); i++) {
res.add(v[i], v[i - 1], l);
}
int id = res.findmin();
int ans = 0;
for (int i = 0; i < N; i++) {
ans = max(ans, res.max_dist[0][i]);
}
return ans;
}
