#include "dreaming.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
vector<pair<int, int>> graph[100001];
int dp[100001], component[100001], fin[100001];
bool visited[100001];
void dfs1(int node, int indx, int parent = -1) {
visited[node] = true;
component[node] = indx;
for (auto& i : graph[node]) {
if (i.first == parent) continue;
dfs1(i.first, indx, node);
}
}
void dfs(int super, int node, int cost = 0, int parent = -1) {
for (auto& i : graph[node]) {
if (i.first == parent) continue;
dfs(super, i.first, cost + i.second, node);
dp[super] = max(dp[super], cost + i.second);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
fill(fin, fin + N, INT_MAX);
FOR(i, 0, M) {
graph[A[i]].push_back({B[i], T[i]});
graph[B[i]].push_back({A[i], T[i]});
}
int indx = 0;
FOR(i, 0, N) {
if (!visited[i]) dfs1(i, indx++);
}
// FOR(i, 0, N) cout << component[i] << ' ';
// cout << '\n';
FOR(i, 0, N) dfs(i, i);
// FOR(i, 0, N) cout << dp[i] << ' ';
// cout << '\n';
FOR(i, 0, N) fin[component[i]] = min(fin[component[i]], dp[i]);
sort(fin, fin + indx, greater<int>());
// cout << fin[0] << ' ' << fin[1] << ' ' << fin[2] << '\n';
return max(fin[0], max(fin[0] + fin[1] + (indx > 1) * L, fin[1] + fin[2] + 2 * (indx > 2) * L));
}
