#include <bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define endl "\n"
using namespace std;
vector<vector<pair<int, ll>>> adj;
vector<pair<ll, int>> dp1, dp2, path;
vector<int> pt, used;
void dfsf(int v, int e){
used[v] = 1;
pt.push_back(v);
for(auto &u : adj[v]){
if(u.first == e) continue;
dfsf(u.first, v);
ll val = dp1[u.first].first + u.second;
if(val >= dp1[v].first){
dp2[v] = dp1[v];
dp1[v] = {val, u.first};
} else if(val >= dp2[v].first){
dp2[v] = {val, u.first};
}
}
}
void dfss(int v, int e){
for(auto &u : adj[v]){
if(u.first == e) continue;
ll val;
if(u.first == dp1[v].second) val = dp2[v].first + u.second;
else val = dp1[v].first + u.second;
if(val >= dp1[u.first].first){
dp2[u.first] = dp1[u.first];
dp1[u.first] = {val, v};
} else if(val >= dp2[u.first].first){
dp2[u.first] = {val, v};
}
dfss(u.first, v);
}
}
void prepare(int pos){
pt.clear();
dfsf(pos, -1);
dfss(pos, -1);
ll mx = 0;
for(int v : pt){
mx = max(mx, dp1[v].first + dp2[v].first);
}
int idx = -1;
ll mn = LLONG_MAX;
for(int v : pt){
ll val = dp1[v].first + dp2[v].first;
if(val == mx){
ll x = max(dp1[v].first, dp2[v].first);
if(x < mn){
mn = x;
idx = v;
}
}
}
path.push_back({mn, idx});
}
int travelTime(int N, int M, int L, int a[], int b[], int t[]){
adj.assign(N, vector<pair<int, ll>>());
dp1.assign(N, {0, -1});
dp2.assign(N, {0, -1});
used.assign(N, 0);
path.clear();
for(int i = 0; i < M; i++){
int x = a[i], y = b[i];
ll z = t[i];
adj[x].push_back({y, z});
adj[y].push_back({x, z});
}
for(int i = 0; i < N; i++){
if(!used[i]) prepare(i);
}
sort(path.begin(), path.end(), greater<pair<ll, int>> ());
for(int i = 1; i < path.size(); i++){
int x = path[i].second, y = path[0].second;
adj[x].push_back({y, (ll)L});
adj[y].push_back({x, (ll)L});
}
for(int i = 0; i < N; i++){
dp1[i] = dp2[i] = {0, -1};
}
pt.clear();
dfsf(0, -1);
dfss(0, -1);
ll mx = 0;
for(int i = 0; i < N; i++){
mx = max(mx, dp1[i].first);
}
return mx;
}
