#include "dreaming.h"
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define inf 1000000000
using namespace std;
typedef long long ll;
vector<pair<ll, ll>> graf[200005];
ll ob[200005];
ll mx[200005];
ll mx1[200005];
ll ixm[200005];
ll rez = 0;
ll dfs(ll u, ll p = -1)
{
ob[u] = 1;
ll ix = 0;
for (auto [v, w] : graf[u])
{
if (v != p)
{
ll tr = dfs(v, u)+w;
if (tr > mx[u])
{
mx1[u] = max(mx1[u], mx[u]);
mx[u] = tr;
ixm[u] = ix;
}
else
mx1[u] = max(mx1[u], tr);
}
ix++;
}
return mx[u];
}
ll getBest(ll u, ll trd, ll p = -1)
{
ll tr = max(trd, mx[u]);
rez = max(rez, mx[u]+max(trd, mx1[u]));
for (int i = 0; i < graf[u].size(); i++)
{
if (graf[u][i].first == p)
continue;
if (i == ixm[u])
{
tr = min(tr, getBest(graf[u][i].first, max(trd, mx1[u])+graf[u][i].second, u));
continue;
}
tr = min(tr, getBest(graf[u][i].first, max(trd, mx[u])+graf[u][i].second, u));
}
return tr;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
memset(ixm, -1, sizeof(ixm));
for (ll i = 0; i < m; i++)
{
graf[a[i]].push_back({b[i], t[i]});
graf[b[i]].push_back({a[i], t[i]});
}
priority_queue<ll> pq;
for (ll i = 0; i < n; i++)
if (!ob[i])
{
dfs(i);
ll tr = getBest(i, 0);
pq.push(tr);
}
ll tr = pq.top();
pq.pop();
if (pq.size())
tr += pq.top()+l;
rez = max(rez, tr);
if (pq.size() > 1)
{
tr = pq.top();
pq.pop();
tr += pq.top();
tr += 2*l;
rez = max(rez, tr);
}
return rez;
}
