#include "dreaming.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
const int maxn = 100100;
int n;
vector<pi> g[maxn];
pi dp[maxn];
int vis[maxn];
ll d;
void dfs(int v) {
ll x, y;
x=y=0;
vis[v] = 1;
for(auto i: g[v]) {
if(vis[i.first]) continue;
dfs(i.first);
ll t = i.second + dp[i.first].first;
if(x<t) y = x, x = t;
else if(y < t) y = t;
}
dp[v] = {x, y};
}
void findd(int v, int p, ll len = 0) {
d = min(d, max(len, dp[v].first));
for(auto i : g[v]) {
if(i.first==p) continue;
ll x = len+i.second;
if(dp[i.first].first+i.second!=dp[v].first) x = max(x, dp[v].first+i.second);
else x = max(x, dp[v].second+i.second);
findd(i.first, v, x);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
if(n==1) return 0;
for(int i = 0; i < M; i++) {
g[A[i]].pb({B[i], T[i]});
g[B[i]].pb({A[i], T[i]});
}
vector<ll> x;
for(int i = 0; i < n; i++) {
if(vis[i]) continue;
dfs(i);
d = 1e17;
findd(i, i);
x.pb(d);
}
sort(x.rbegin(), x.rend());
ll ans = x[0];
if(x.size()>1) ans = max(ans, x[0]+L+x[1]);
if(x.size()>2) ans = max(ans, x[2]+L+L+x[1]);
return ans;
}
