#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
#define MAXN (100005)
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<pair<ll,ll> > v[N];
for(ll i = 0;i < M;i++){
ll a,b,c;
a = A[i];
b = B[i];
c = T[i];
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
}
vector<pair<ll,ll> > ans;
vector<ll> component[N];
queue<ll> q;
ll dist[N];
ll dist2[N];
ll dist3[N];
ll dist4[N];
int visited[N];
int visited2[N];
int visited3[N];
int visited4[N];
memset(dist,0,sizeof(dist));
memset(visited,0,sizeof(visited));
memset(dist2,0,sizeof(dist2));
memset(visited2,0,sizeof(visited2));
memset(dist3,0,sizeof(dist3));
memset(visited3,0,sizeof(visited3));
memset(dist4,0,sizeof(dist4));
memset(visited4,0,sizeof(visited4));
for(ll i = 0;i < N;i++){
if(visited[i] != 0){
continue;
}
q.push(i);
dist[i] = 0;
component[i].push_back(i);
visited[i] = 1;
while(!q.empty()){
ll a = q.front();
q.pop();
visited[a] = 1;
for(auto u : v[a]){
if(visited[u.first] == 0 || dist[a] + u.second < dist[u.first]){
if(visited[u.first] == 0){
component[i].push_back(u.first);
}
q.push(u.first);
dist[u.first] = dist[a] + u.second;
visited[u.first] = 1;
}
}
}
ll index = 0;
ll num = 0;
for(ll j = 0;j < component[i].size();j++){
ll a = component[i][j];
if(dist[a] > num){
num = dist[a];
index = a;
}
}
q.push(index);
dist2[index] = 0;
visited2[index] = 1;
ll sum = 0;
while(!q.empty()){
ll a = q.front();
q.pop();
visited2[a] = 1;
for(auto u : v[a]){
if(visited2[u.first] == 0 || dist2[a] + u.second < dist2[u.first]){
q.push(u.first);
dist2[u.first] = dist2[a] + u.second;
visited2[u.first] = 1;
}
}
}
ll index2 = 0;
for(ll j = 0;j < component[i].size();j++){
ll a = component[i][j];
if(dist2[a] > sum){
index2 = a;
sum = dist2[a];
}
}
q.push(index);
dist3[index] = 0;
visited3[index] = 1;
while(!q.empty()){
ll a = q.front();
q.pop();
visited3[a] = 1;
for(auto u : v[a]){
if(visited3[u.first] == 0 || dist3[a] + u.second < dist3[u.first]){
q.push(u.first);
dist3[u.first] = dist3[a] + u.second;
visited3[u.first] = 1;
}
}
}
q.push(index2);
dist4[index2] = 0;
visited4[index2] = 1;
while(!q.empty()){
ll a = q.front();
q.pop();
visited4[a] = 1;
for(auto u : v[a]){
if(visited4[u.first] == 0 || dist4[a] + u.second < dist4[u.first]){
q.push(u.first);
dist4[u.first] = dist4[a] + u.second;
visited4[u.first] = 1;
}
}
}
pair<ll,ll> maximum = make_pair(-1,0);
for(ll j = 0;j < component[i].size();j++){
ll a = component[i][j];
if(maximum.first == -1 || max(dist3[a],dist4[a]) < maximum.first){
maximum.first = max(dist3[a],dist4[a]);
maximum.second = a;
}
}
ans.push_back(make_pair(maximum.first,maximum.second));
}
sort(ans.begin(),ans.end(),greater<pair<ll,ll> >());
for(ll i = 1;i < ans.size();i++){
ll a = ans[0].second;
ll b = ans[i].second;
v[a].push_back(make_pair(b,L));
v[b].push_back(make_pair(a,L));
}
memset(dist,0,sizeof(dist));
memset(visited,0,sizeof(visited));
memset(dist2,0,sizeof(dist2));
memset(visited2,0,sizeof(visited2));
q.push(0);
dist[0] = 0;
visited[0] = 1;
while(!q.empty()){
ll a = q.front();
q.pop();
visited[a] = 1;
for(auto u : v[a]){
if(visited[u.first] == 0 || dist[a] + u.second < dist[u.first]){
q.push(u.first);
dist[u.first] = dist[a] + u.second;
visited[u.first] = 1;
}
}
}
ll index = 0;
ll num = 0;
for(ll i = 0;i < N;i++){
if(dist[i] > num){
num = dist[i];
index = i;
}
}
q.push(index);
dist2[index] = 0;
visited2[index] = 1;
ll sum = 0;
while(!q.empty()){
ll a = q.front();
q.pop();
visited2[a] = 1;
for(auto u : v[a]){
if(visited2[u.first] == 0 || dist2[a] + u.second < dist2[u.first]){
q.push(u.first);
dist2[u.first] = dist2[a] + u.second;
visited2[u.first] = 1;
}
}
}
for(ll i = 0;i < N;i++){
if(dist2[i] > sum){
sum = dist2[i];
}
}
return sum;
}
