#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5;
vector<pair<int,int>> g[maxn];
bool vis[maxn],idx[maxn];
vector<int> c;
int sz[maxn],mx,to,used[maxn],cst[maxn][2],t,best,mn;
void path(int u,int cost){
idx[u] = vis[u] = 1;
if(cost > mx){
mx = cost;
to = u;
}
for(pair<int,int> cur : g[u]){
int v = cur.first;
int w = cur.second;
if(vis[v])continue;
path(v,cost + w);
}
}
void dfs(int u,int cost){
vis[u] = 1;
cst[u][t] = cost;
if(t == 1){
if(max(cst[u][0],cst[u][1]) < mn){
mn = max(cst[u][0],cst[u][1]);
best = u;
}
}
for(pair<int,int> cur : g[u]){
int v = cur.first;
int w = cur.second;
if(vis[v])continue;
dfs(v,cost + w);
}
}
void find(int s){
mn = 2e9;
mx = 0;
memset(vis,0,sizeof(vis));
path(s,0);
t = 0;
memset(vis,0,sizeof(vis));
dfs(to,0);
memset(vis,0,sizeof(vis));
mx = 0;
path(to,0);
t = 1;
memset(vis,0,sizeof(vis));
dfs(to,0);
s = best;
c.push_back(s);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++){
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<N;i++)
if(!idx[i])
find(i);
for(int i=1;i<c.size();i++){
g[c[i]].push_back({c[0],L});
g[c[0]].push_back({c[i],L});
}
memset(vis,0,sizeof(vis));
mx = 0;
path(0,0);
memset(vis,0,sizeof(vis));
mx = 0;
path(to,0);
return mx;
}
