#include "dreaming.h"
#include<bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
using namespace std;
vector<pii>g[100005], cts;
int dis[100005], mx, mxx, p[100005], c;
bool used[100005];
void dfs(int v, int par)
{
used[v]=1;
for(pii u : g[v])
if(u.F!=par)
{
p[u.F]=v;
dis[u.F]=dis[v]+u.S;
if(dis[u.F]>dis[mx]) mx=u.F;
dfs(u.F, v);
}
}
void path(int v)
{
//cout<<v<<' '<<max(dis[mx]-dis[v], dis[v])<<' '<<c<<' '<<max(dis[mx]-dis[c], dis[c])<<endl;
if(max(dis[mx]-dis[v], dis[v])<max(dis[mx]-dis[c], dis[c]))
c=v;
if(p[v]==v) return;
path(p[v]);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
for(int i=0; i<m; i++)
{
g[A[i]+1].pb({B[i]+1, T[i]});
g[B[i]+1].pb({A[i]+1, T[i]});
}
//cout<<endl;
for(int i=1; i<=n; i++)
if(!used[i])
{
//cout<<i<<endl;
mx=i; dis[i]=0;
dfs(i, 0); mxx=mx;
//cout<<mx<<endl;
dis[mxx]=0; p[mxx]=mxx; mx=i;
dfs(mxx, 0);
//cout<<mx<<endl;
c=mx;
path(mx);
//cout<<c<<endl<<endl;
cts.pb({max(dis[mx]-dis[c], dis[c]), c});
}
sort(cts.begin(), cts.end());
//cout<<endl<<cts[cts.size()-1].F<<' '<<cts[cts.size()-1].S<<endl;
for(int i=0; i<(int)cts.size()-1; i++)
{
g[cts[i].S].pb({cts[cts.size()-1].S, L});
g[cts[cts.size()-1].S].pb({cts[i].S, L});
}
/*
cout<<endl;
for(int i=1; i<=n; i++)
{
cout<<i<<" ->\n";
for(pii u : g[i]) cout<<u.F<<' '<<u.S<<endl;
cout<<endl;
}
*/
mx=1, dis[1]=0;
dfs(1, 0); mxx=mx;
dis[mxx]=0; mx=0;
dfs(mxx, 0);
return dis[mx];
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
