#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
bool vis[MAXN];
int n, m, l;
vector<pll> adj[MAXN];
ll dist[2][MAXN];
vector<int> C;
void dfs(int v, int p, int c, ll d) {
dist[c][v] = d;
vis[v] = true;
C.push_back(v);
for (auto [u, l] : adj[v])
if (u != p)
dfs(u, v, c, d + l);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, l = L;
for (int i = 0; i < m; i++) {
A[i]++;
B[i]++;
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
ll ans = 0;
vector<ll> vec;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
C.clear();
dfs(i, 0, 0, 0);
int v = i;
for (int e : C)
if (dist[0][e] > dist[0][v])
v = e;
C.clear();
dfs(v, 0, 1, 0);
int u = i;
for (int e : C)
if (dist[1][e] > dist[1][u])
u = e;
ans = max(ans, dist[1][u]);
C.clear();
dfs(u, 0, 0, 0);
int c = u;
for (int e : C)
if (max(dist[0][e], dist[1][e]) < max(dist[0][c], dist[1][c]))
c = e;
vec.push_back(max(dist[0][c], dist[1][c]));
}
sort(vec.begin(), vec.end());
while (int(vec.size() > 1)) {
ll x = vec.back();
vec.pop_back();
ll y = vec.back();
vec.pop_back();
ans = max(ans, x + y + L);
vec.push_back(max(x, y + L));
}
return ans;
}
