#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vector < vector < pair < int, ll > > > adj (n);
for (int i = 0; i < m; ++i)
{
adj[a[i]].push_back ({ b[i], (ll) t[i] });
adj[b[i]].push_back ({ a[i], (ll) t[i] });
}
vector < bool > vi (n);
vector < tuple < ll, ll, ll > > dd (n);
auto dfs1 = [&] (auto self, int v, int p) -> ll
{
vi[v] = true;
auto &[x, m, y] = dd[v];
m = -1;
for (auto &c : adj[v])
if (c.first != p)
{
ll z = self (self, c.first, v) + c.second;
if (z > x) y = x, x = z, m = c.first;
else if (z > y) y = z;
}
return x;
};
auto dfs2 = [&] (auto self, int v, int p, ll z) -> pair < ll, ll >
{
auto &[x, m, y] = dd[v];
if (z > x) y = x, x = z, m = p;
else if (z > y) y = z;
pair < ll, ll > ans = { x, v };
for (auto &c : adj[v])
if (c.first != p)
ans = min (ans, self (self, c.first, v, (c.first == m ? y : x) + c.second));
return ans;
};
vector < pair < ll, int > > v;
for (int i = 0; i < n; ++i)
if (!vi[i])
dfs1 (dfs1, i, -1), v.push_back ({ 0, dfs2 (dfs2, i, -1, 0).second });
for (auto &k : v) k.first = get < 0 > (dd[k.second]);
sort (v.rbegin (), v.rend ());
ll ii = 0;
auto &[ix, im, iy] = dd[v[0].second];
for (auto &[_k, k] : v)
{
if (!ii++) continue;
auto &[x, m, y] = dd[k];
auto jx = x, jy = y;
if (ix + (ll) l > jx) jy = jx, jx = ix + (ll) l;
else if (ix + (ll) l > jy) jy = ix + (ll) l;
if (iy + (ll) l > jy) jy = iy + (ll) l;
if (x + (ll) l > ix) iy = ix, ix = x + (ll) l;
else if (x + (ll) l > iy) iy = x + (ll) l;
if (y + (ll) l > iy) iy = y + (ll) l;
if (jx < ix) ix = jx, iy = jy;
}
return ix + iy;
}
