// Fluixarata or Cyngulini?
// That is the question...
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int v, int p, int dp[], bool odw[], vector<pair<int,int>> tree[], int &maks) {
dp[v] = 0, odw[v] = true;
int x = 0, y = 0;
for (auto [u,w] : tree[v]) {
if (u == p)
continue;
dfs(u,v,dp,odw,tree,maks), dp[v] = max(dp[v],dp[u]+w);
if (dp[u]+w > x)
y = x, x = dp[u]+w;
else if (dp[u]+w > y)
y = dp[u]+w;
}
maks = max(maks,x+y);
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
bool odw[n+1]; fill(odw,odw+n+1,false);
int dp[n+1], inf = (1<<30), x = -inf, y = -inf, z = -inf;
vector<pair<int,int>> tree[n+1];
for (int i = 0; i < m; i++)
tree[A[i]+1].push_back({B[i]+1,T[i]}), tree[B[i]+1].push_back({A[i]+1,T[i]});
for (int i = 1; i <= n; i++) {
if (odw[i])
continue;
int maks = 0;
dfs(i,0,dp,odw,tree,maks);
if (maks > x)
z = y, y = x, x = maks;
else if (maks > y)
z = y, y = maks;
else if (maks > z)
z = maks;
}
return max({x,(x+1)/2+(y+1)/2+l,(y+1)/2+(z+1)/2+2*l});
}
