#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
typedef pair < ll , ll > pll;
vector < vector < pll > > g;
vector < bool > vis;
vector < pll > b;
ll dfs1(int x, int pa=-1)
{
vis[x] = true;
b[x] = {0, 0};
for (auto [y, w] : g[x]) if (y != pa)
{
ll temp = dfs1(y, x) + w;
if (b[x].second < temp) b[x].second = temp;
if (b[x].first < b[x].second) swap(b[x].first, b[x].second);
}
return b[x].first;
}
ll dfs2(int x, ll w = 0, int pa=-1)
{
ll bes;
if (pa == -1)
{
bes = b[x].first;
}
else
{
ll up = b[pa].first;
if (up == b[x].first + w) up = b[pa].second;
up += w;
if (up > b[x].second)
{
b[x].second = up;
}
if (b[x].second > b[x].first) swap(b[x].second, b[x].first);
bes = b[x].first;
}
for (auto [y, w] : g[x]) if (y != pa)
{
bes = min(bes, dfs2(y, w, x));
}
return bes;
}
ll calc(int x)
{
dfs1(x);
return dfs2(x);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
g.resize(N);
vis.resize(N, false);
b.resize(N, {0, 0});
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]});
}
ll g1=0, g2=0, g3=0;
for (int x = 0; x < N; x++) if (!vis[x])
{
ll temp = calc(x);
if (temp > g1)
{
g3 = g2;
g2 = g1;
g1 = temp;
}
else if (temp > g2)
{
g3 = g2;
g2 = temp;
}
else if (temp > g3)
{
g3 = temp;
}
}
ll ans = g1 + g2 + L;
ans = max(ans, g2 + g3 + L + L);
return ans;
}
