#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include"dreaming.h"
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 79, inf = 1e9 + 79;
vector<int> vis(maxn, 0), dp(maxn, 0);
vector<vector<pair<int, int> > > g(maxn);
void dfs1(int u, int p)
{
vis[u] = 1;
for (int i = 0; i < g[u].size(); i++) if (g[u][i].first == p) { g[u].erase(g[u].begin() + i); break; }
for (pair<int, int> i : g[u])
{
dfs1(i.first, u);
dp[u] = max(dp[u], dp[i.first] + i.second);
}
}
void dfs2(int u, int dist, int &mini, int &dia)
{
mini = min(mini, max(dist, dp[u]));
vector<int> pf(g[u].size() + 1, 0), sf(g[u].size() + 1, 0);
pair<int, int> p(0, 0);
for (int i = 0; i < g[u].size(); i++)
{
int di = dp[g[u][i].first] + g[u][i].second; pf[i + 1] = max(pf[i], di);
if (di > p.first) swap(p.first, p.second), p.first = di;
else if (di > p.second) p.second = di;
}
dia = max({ dia, p.first + p.second, dp[u] + dist });
for (int i = g[u].size() - 1; i >= 0; i--)
sf[i] = max(sf[i + 1], dp[g[u][i].first] + g[u][i].second);
for (int i = 0; i < g[u].size(); i++)
dfs2(g[u][i].first, max({ dist, pf[i], sf[i + 1] }) + g[u][i].second, mini, dia);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
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] });
vector<int> v; int ans = 0;
for (int i = 0; i < n; i++)
if (!vis[i])
{
v.push_back(inf);
dfs1(i, -1), dfs2(i, 0, v.back(), ans);
}
sort(v.begin(), v.end(), greater<int>());
if (v.size() > 1) ans = max(ans, v[0] + l + v[1]);
if (v.size() > 2) ans = max(ans, v[1] + 2 * l + v[2]);
return ans;
}
