#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 100001;
const int INF = INT_MAX;
vector<pair<int,int>>G[N];
void add(int u,int v,int w)
{
G[u].push_back({v,w});
G[v].push_back({u,w});
}
bool vis[N];
vector<int>all;
void dfs(int v)
{
all.push_back(v);
vis[v]=1;
for(pair<int,int> nxt : G[v])
{
int u=nxt.first;
if(!vis[u]) dfs(u);
}
}
int dis[N];
pair<int,int>get(int v)
{
for(int u : all) dis[u]=INF;
queue<int>q;
q.push(v);
dis[v]=0;
while(!q.empty())
{
int node=q.front();
q.pop();
for(pair<int,int> nxt : G[node])
{
int u=nxt.first;
int w=nxt.second;
if(dis[node]+w<dis[u])
{
dis[u]=dis[node]+w;
q.push(u);
}
}
}
pair<int,int>res={-INF,-INF};
for(int u : all) res=max(res,{dis[u] , v});
return res;
}
pair<int,int> find_center()
{
vector<pair<int,int>>srt;
for(int v : all) srt.push_back(get(v));
sort(srt.begin(),srt.end());
return {srt[0].second , srt[0].first};
}
int travelTime(int N , int M , int L , int A[] , int B[] , int T[])
{
for(int i = 0;i < M;i++) add(A[i] , B[i] , T[i]);
vector < pair < int , int > > srt;
for(int i = 0;i < N;i++)
{
if(vis[i]) continue;
all.clear();
dfs(i);
pair < int , int > cw = find_center();
int center = cw.first;
int max_w = cw.second;
srt.push_back({max_w , center});
}
sort(srt.rbegin() , srt.rend());
for(int i = 1;i < srt.size();i++) add(srt[0].second , srt[i].second , L);
all.clear();
for(int i = 0;i < N;i++) all.push_back(i);
int res = -INF;
for(int i = 0;i < N;i++) res = max(res , get(i).first);
return res;
}
