#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define fi first
#define se second
#define mpr make_pair
#define inf 0x3F3F3F3F
const int MXN = 1e5 + 5;
int n, m, l;
vector<pii> adj[MXN];
vector<vector<int>> comp;
int used[MXN];
int dist[2][MXN];
int c = -1;
int mx, node = -1;
int dia1, dia2;
void dfs(int a)
{
comp[c].pb(a);
used[a] = 1;
for (pii v : adj[a])
{
if (used[v.fi]) continue;
dfs(v.fi);
}
}
void dfs1(int a, int w = 0, int p = -1)
{
if (w > mx)
{
mx = w;
dia2 = a;
}
for (pii v : adj[a])
{
if (v.fi == p) continue;
dfs1(v.fi, w + v.se, a);
}
}
void dfs2(int a, int id, int w = 0, int p = -1)
{
dist[id][a] = w;
for (pii v : adj[a])
{
if (v.fi == p) continue;
dfs2(v.fi, id, w + v.se, a);
}
}
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++)
{
adj[A[i]].pb(mpr(B[i], T[i]));
adj[B[i]].pb(mpr(A[i], T[i]));
}
for (int i = 0; i < n; i++)
{
if (!used[i])
{
c++;
comp.pb(vector<int> (0));
dfs(i);
}
}
multiset<int> ms;
int mx1 = -inf;
for (int i = 0; i <= c; i++)
{
mx = -inf;
dia1 = dia2 = -1;
dfs1(comp[i][0]);
mx = -inf;
dia1 = dia2;
dfs1(dia1);
dfs2(dia1, 0);
dfs2(dia2, 1);
int center = comp[i][0];
for (int u : comp[i])
{
if (max(dist[0][u], dist[1][u]) < max(dist[0][center], dist[1][center])) center = u;
}
ms.ins(max(dist[0][center], dist[1][center]));
mx1 = max(mx1, mx);
}
if (!c) return max(mx1, *ms.begin());
auto it = ms.end();
it--;
it--;
auto it1 = it;
it1--;
if (c == 1) return max(mx1, *ms.rbegin() + *it + l);
return max({mx1, *ms.rbegin() + *it + l, *it + *it1 + 2*l});
}
