#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 100001;
const int INF = INT_MAX;
int n;
vector<pair<int,int>>G[N];
map<pair<int,int>,int>dsc;
void add(int u,int v,int w)
{
dsc[{u,v}]=w;
dsc[{v,u}]=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] , u});
return res;
}
vector<int> get_path(int u,int v)
{
for(int u : all) dis[u]=INF;
queue<int>q;
q.push(u);
dis[u]=0;
while(!q.empty())
{
int node=q.front();
q.pop();
for(pair<int,int> nxt : G[node])
{
int u=nxt.first;
if(dis[node]+1<dis[u])
{
dis[u]=dis[node]+1;
q.push(u);
}
}
}
vector<int>res;
int cur_node=v;
while(1)
{
res.push_back(v);
if(v==u) break;
int mn=INF;
for(pair<int,int> node : G[v]) mn=min(mn,dis[node.first]);
for(pair<int,int> node : G[v])
{
if(dis[node.first]==mn)
{
v=node.first;
break;
}
}
}
return res;
}
pair<int,int> find_center()
{
pair<int,int>mx1=get(all[0]);
pair<int,int>mx2=get(mx1.second);
int u=mx1.second;
int v=mx2.second;
int tot=mx2.first;
int cur=0;
vector<int>path=get_path(u,v);
if(path.size()==1)
{
return {path[0],0};
}
vector<pair<int,int>>srt;
for(int i=1;i<path.size();i++)
{
int wg=dsc[{path[i-1],path[i]}];
cur+=wg;
tot-=wg;
srt.push_back({max(cur,tot),path[i]});
}
sort(srt.begin(),srt.end());
return {srt[0].second,srt[0].first};
}
pair<int,int> get_mx(int v)
{
vector<int>d(n,INF);
queue<int>q;
d[v]=0;
q.push(v);
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(d[node]+w<d[u])
{
d[u]=d[node]+w;
q.push(u);
}
}
}
pair<int,int>res;
for(int i=0;i<n;i++) res=max(res,{d[i],i});
return res;
}
int get_dia()
{
pair<int,int>mx1=get_mx(0);
pair<int,int>mx2=get_mx(mx1.second);
return mx2.first;
}
int travelTime(int N , int M , int L , int A[] , int B[] , int T[])
{
n = N;
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);
return get_dia();
}
