#include "dreaming.h"
#include <vector>
#include <iostream>
#include <algorithm>
#define X first
#define Y second
using namespace std;
const int MAXN = 100100;
int dp1[MAXN], dp2[MAXN];
vector<pair<int, int>> v[MAXN];
int n, m, l;
int used[MAXN];
int ba;
vector<int> vr;
void dfs1(int beg, int par)
{
used[beg] = 1;
for (pair<int, int> nb : v[beg])
{
if (nb.X == par)
continue;
dfs1(nb.X, beg);
dp1[beg] = max(dp1[beg], dp1[nb.X] + nb.Y);
}
}
void dfs2(int beg, int par)
{
int ans = dp2[beg];
vector<pair<int, int>> kids;
for (pair<int, int> nb : v[beg])
{
if (nb.X == par)
continue;
ans = max(ans, nb.Y + dp1[nb.X]);
kids.push_back({nb.X, nb.Y});
}
ba = min(ba, ans);
int sz = kids.size();
if (sz == 0)
return;
vector<int> pref(sz), sufx(sz);
pref[0] = kids[0].Y + dp1[kids[0].X];
for (int i = 1; i < sz; i++)
{
pref[i] = max(pref[i - 1], kids[i].Y + dp1[kids[i].X]);
}
sufx[sz - 1] = kids[sz - 1].Y + dp1[kids[sz - 1].X];
for (int i = sz - 2; i >= 0; i--)
{
sufx[i] = max(sufx[i + 1], kids[i].Y + dp1[kids[i].X]);
}
for (int i = 0; i < sz; i++)
{
int nb = kids[i].X;
int val = dp2[beg];
if (i - 1 >= 0)
val = max(val, pref[i - 1]);
if (i + 1 < sz)
val = max(val, sufx[i + 1]);
dp2[nb] = kids[i].Y + val;
dfs2(nb, beg);
}
}
void check(int i)
{
if (used[i]==1)
return;
ba = 1e9+5;
dfs1(i, n);
dfs2(i, n);
if(ba==1e9+5)vr.push_back(0);
else vr.push_back(ba);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
vr.clear();
n = N;
m = M;
l = L;
for (int i = 0; i < n; i++)
{
dp1[i]=dp2[i]=0;
used[i] = 0;
v[i].clear();
}
for (int i = 0; i < m; i++)
{
v[A[i]].push_back({B[i], T[i]});
v[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < n; i++)
check(i);
sort(vr.rbegin(), vr.rend());
if (vr.size() == 1)
return vr[0];
if (vr.size() == 2)
return vr[0] + vr[1] + l;
return max(vr[0] + vr[1] + l, vr[1] + l + vr[2] + l);
}
