#include "dreaming.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef pair<int,int> pii;
const int maxn=1e5+10;
bool bio[maxn];
int dist[maxn];
int dp[maxn];
vector<pii> g[maxn];
void dfs1(int cvor){
if(bio[cvor]) return;
bio[cvor]=true;
dp[cvor]=0;
for(pii i:g[cvor]){
if(bio[i.xx]) continue;
dfs1(i.xx);
dp[cvor]=max(dp[cvor],dp[i.xx]+i.yy);
}
}
void uradi(int cvor,int prosli){
dp[prosli]=dp[cvor]=0;
for(auto i:g[prosli]){
if(i.xx==cvor) continue;
dp[prosli]=max(dp[prosli],dp[i.xx]+i.yy);
}
for(auto i:g[cvor]){
dp[cvor]=max(dp[cvor],dp[i.xx]+i.yy);
}
}
pii dfs2(int cvor,int prosli){
if(prosli!=-1) uradi(cvor,prosli);
pii ret={dp[cvor],cvor};
for(pii i:g[cvor]){
if(i.xx==prosli) continue;
ret=min(ret,dfs2(i.xx,cvor));
}
if(prosli!=-1) uradi(prosli,cvor);
return ret;
}
pii najd(int cvor,int prosli){
pii ret=mp(0,cvor);
for(pii i:g[cvor]){
if(i.xx==prosli) continue;
pii pom=najd(i.xx,cvor);
pom.xx+=i.yy;
ret=max(ret,pom);
}
return ret;
}
int odg(int cvor){
return najd(najd(cvor,-1).yy,-1).xx;
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]) {
for(int i=0;i<n;i++) dist[i]=-1;
for(int i=0;i<m;i++){
g[a[i]].pb(mp(b[i],t[i]));
g[b[i]].pb(mp(a[i],t[i]));
}
priority_queue<pii,vector<pii>,greater<pii> > pq;
for(int i=0;i<n;i++){
if(bio[i]) continue;
dfs1(i);
pq.push(dfs2(i,-1));
}
while(pq.size()!=1){
pii t1,t2;
t1=pq.top(); pq.pop();
t2=pq.top(); pq.pop();
g[t1.yy].pb(mp(t2.yy,l));
g[t2.yy].pb(mp(t1.yy,l));
if(max(t1.xx,t2.xx+l)<=max(t1.xx+l,t2.xx)) pq.push(mp(max(t1.xx,t2.xx+l),t1.yy));
else pq.push(mp(max(t1.xx+l,t2.xx),t2.yy));
}
return odg(1);
}
