#include <bits/stdc++.h>
#include "dreaming.h"
#define MAX_N 100000
#define xx first
#define yy second
using namespace std;
const int sqrInf = (int)(1e9);
vector <pair<int, int>> g[MAX_N + 1];
void add(int a, int b, int c)
{
g[a].push_back({b, c});
}
int k;
int mn;
int dist[MAX_N + 1];
int dp[MAX_N + 1];
int st[MAX_N + 1];
int dr[MAX_N + 1 + 1];
int nod[MAX_N + 1];
int dst[MAX_N + 1];
int xxa[MAX_N + 1];
int viz[MAX_N + 1];
int n;
void dfs(int a)
{
viz[a] = 1;
for(auto u : g[a])
{
if(viz[u.xx] == 0)
{
dfs(u.xx);
dp[a] = max(dp[a], u.yy + dp[u.xx]);
}
}
}
int rez;
void dfsDist(int a, int tata, int d)
{
int w = max(d, dp[a]);
mn = min(mn, w);
vector <int> t2;
t2.clear();
int x = 0;
for(auto u : g[a])
{
if(u.xx != tata)
{
t2.push_back(u.xx);
nod[++ x] = u.xx;
dst[x] = u.yy;
xxa[x] = dp[u.xx] + u.yy;
}
}
st[1] = xxa[1];
for(int i = 2; i <= x; i ++)
st[i] = max(st[i - 1], xxa[i]);
dr[x] = xxa[x];
for(int i = x - 1; i >= 1; i --)
dr[i] = max(dr[i + 1], xxa[i]);
vector <int> tmp;
tmp.clear();
st[0] = dr[x + 1] = 0;
for(int i = 1; i <= x; i ++)
tmp.push_back(max({d, st[i - 1], dr[i + 1]}) + dst[i]);
sort(xxa + 1, xxa + x + 1);
if(x > 1)
rez = max(rez, xxa[x] + xxa[x - 1]);\
rez = max(rez, dp[a] + d);
int i = 0;
for(auto u : t2)
{
i ++;
dfsDist(u, a, tmp[i - 1]);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n = N;
for(int i = 0; i < M; i ++)
{
int a = A[i] + 1;
int b = B[i] + 1;
add(a, b, T[i]);
add(b, a, T[i]);
}
for(int i = 1; i <= n; i ++)
{
if(viz[i] == 0)
{
dfs(i);
// cout << " AVEM COMP " << i << " " << dp[i] << "\n";
mn = sqrInf;
dfsDist(i, -1, 0);
dist[++ k] = mn;
// cout << "ACEASTA COMP ARE DISTR MAX " << dist[k] << "\n";
}
}
sort(dist + 1, dist + k + 1);
// cout << rez << " " << dist[k] << " " << dist[k - 1] << " " << dist[k - 2] << "\n";
return max(rez, (k == 1 ? dist[k] :
(k == 2 ? dist[k] + dist[k - 1] + L : max(dist[k] + dist[k - 1] + L, dist[k - 1] + dist[k - 2] + (L << 1)))));
}
