#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
vector<vector<ll>> dp;
vector<ll> stmp;
vector<bool> vis;
ll n, m, l;
void dfs(ll u, ll p){
vis[u]=1;
if (A[u].size()==1 and u!=p){
dp[u] = {0};
}
for (auto i:A[u]){
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
dfs(v, u);
for (auto ch:dp[v]){
dp[u].push_back(ch+e[i].ff);
}
}
sort(dp[u].rbegin(), dp[u].rend());
while (dp[u].size()>2) dp[u].pop_back();
}
void dfs2(ll u, ll p, ll &diam, ll &big, ll pass){
// cout << u << endl;
dp[u].push_back(pass);
sort(dp[u].rbegin(), dp[u].rend());
while (dp[u].size()>2) dp[u].pop_back();
for (auto i:A[u]){
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
if (dp[u][0]==dp[v][0]+e[i].ff){
dfs2(v, u, diam, big, dp[u][1]+e[i].ff);
}else{
dfs2(v, u, diam, big, dp[u][0]+e[i].ff);
}
}
// cout << u << " <> " << dp[u][0] << ln;
if (dp[u].size()==1){
diam=max(diam, dp[u][0]);
big=0;
return;
}
diam=max(diam, dp[u][0]+dp[u][1]);
big=min(big, dp[u][0]);
}
pair<ll, ll> fout(ll mem){
dfs(mem, mem);
ll diam=0, big=2e18;
dfs2(mem, mem, diam, big, 0);
// cout << mem << " -> " << diam << " " << big << endl;
return {diam, big};
}
int travelTime(int N, int M, int L, int U[], int V[], int W[]) {
n=N; m=M; l=L;
// cout << N << " " << M << " " << L << ln;return 0;
e.resize(m);
A.resize(n);
dp.resize(n);
vis.resize(n);
// return 0;
for (ll i=0; i<m; i++){
A[U[i]].push_back(i);
A[V[i]].push_back(i);
e[i] = {W[i], {U[i], V[i]}};
}
ll ans=0;
vector<ll> bigs;
for (ll i=0; i<n; i++){
// cout << i << ":";
if (!vis[i]){
// cout << i << endl;
auto ret = fout(i);
ans=max(ans, ret.ff);
bigs.push_back(ret.ss);
}
}
sort(bigs.rbegin(), bigs.rend());
ans=max(ans, bigs[0]);
if (bigs.size()>1){
ans=max(ans, bigs[0]+bigs[1]+l);
}
if (bigs.size()>2){
ans=max(ans, bigs[1]+bigs[2]+2*l);
}
return ans;
}
