#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
struct edge {
int v;
int w;
};
const int N = 1e5 + 10;
vector<edge> g[N];
bool mark[N];
int dist[N];
vector<int> component;
int tin[N], tout[N], timer;
int mn;
void dfs(int u) {
if(mark[u]) return;
component.push_back(u);
mark[u] = true;
for(auto v : g[u]) {
if(mark[v.v]) continue;
dist[v.v] = dist[u] + v.w;
dfs(v.v);
}
}
void dfs2(int u, int par) {
tin[u] = timer++;
for(auto v : g[u]) {
if(v.v == par) continue;
dfs2(v.v, u);
}
tout[u] = timer++;
}
bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
void dfs3(int u, int par, int x) {
if(is_ancestor(u, x)) mn = min(mn, max(dist[u], dist[x] - dist[u]));
for(auto v : g[u]) {
if(v.v == par) continue;
dfs3(v.v, u, x);
}
}
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]});
}
vector<int> W, W2;
for(int i = 0; i < n; i++) {
if(mark[i]) continue;
component.clear();
dfs(i);
int mx = i;
for(int j : component) if(dist[j] > dist[mx]) mx = j;
for(int j : component) {
dist[j] = 0;
mark[j] = false;
}
component.clear();
dfs(mx);
int u, v;
u = mx;
mx = i;
for(int j : component) if(dist[j] > dist[mx]) mx = j;
v = mx;
W.push_back(dist[mx]);
dfs2(u, -1);
mn = INT_MAX;
dfs3(u, -1, v);
W2.push_back(mn);
}
int res = 0;
for(int i : W) res = max(res, i);
sort(W2.rbegin(), W2.rend());
if(W2.size() >= 2) res = max(res, W2[0] + W2[1] + l);
if(W2.size() >= 3) res = max(res, W2[1] + W2[2] + 2 * l);
return res;
}
