#include "dreaming.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define lnl long long
#define pii pair<int, int>
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
using namespace std;
int d[3][100010];
int f[100010];
int W[100010];
int w, e, D, R;
int X = -1, Y = -1, Z = -1;
vector<pii> adj[100010];
void dfs(int x, int o)
{
f[x]++;
if (o < 2 && d[o][x] >= D) {e = x; D = d[o][x];}
if (o > 1) D = min(D, max(d[1][x], d[2][x]));
for (auto y: adj[x])
{
if (f[y.F] == o) continue ;
d[o][y.F] = d[o][x] + y.S;
dfs(y.F, o);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
while(M--)
{
adj[A[M]].pb({B[M], T[M]});
adj[B[M]].pb({A[M], T[M]});
}
while(N--)
{
if (f[N]) continue ;
dfs(N, 0);
dfs(e, 1);
R = max(R, D);
dfs(e, 2);
W[w++] = D;
D = 0;
}
while(w--)
{
if (Z < W[w]) Z = W[w];
if (Y < W[w]) {Z = Y; Y = W[w];}
if (X < W[w]) {Y = X; X = W[w];}
}
return max(R, max(X, Z + (Z >= 0) * L) + Y + (Y >= 0) * L);
}
