#include <bits/stdc++.h>
#include "dreaming.h"
#define MAXN 100005
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define max3(a,b,c) max(max(a,b),c)
using namespace std;
//declarations
int N , M , L;
int d[MAXN] , p[MAXN];
bool marc[MAXN] ;
vector<int> radios , vv;
vector<pii> adj[MAXN] ;
//utilities
void ini(int x)
{ vv.resize(0) ; p[x] = -1 ; d[x] = 0 ;}
void dfs(int x)
{
marc[x] = 1 ;
lp(i , 0 , adj[x].size() )
{
int v = adj[x][i].ff ;
if( p[x] == v ) continue ;
d[v] = d[x] + adj[x][i].ss ;
p[v] = x ;
vv.pb(v) ;
dfs(v) ;
}
}
int findMax(int x)
{
lp(i,0,vv.size())
{
int v = vv[i] ;
if(d[v] > d[x]) x = v ;
}
return x ;
}
int findRadio(int diam , int x)
{
int ans = diam ;
for(int i = x ; i != -1 ; i = p[i])
ans = min( ans , max(d[i] , diam - d[i]) ) ;
return ans ;
}
int travelTime( int n , int m , int l , int A[] , int B[] , int T[] )
{
N = n , M = m , L = l;
int ans = 0 ;
lp(i,0,M)
{
int a = A[i] , b = B[i] ;
adj[a].pb( pii(b, T[i]) ) ;
adj[b].pb( pii(a, T[i]) ) ;
}
lp(i,0,N)
if(!marc[i])
{
ini(i) ; dfs(i) ;
int X = findMax(i) ;
ini(X) ; dfs(X) ;
int Y = findMax(X) ;
int diameter = d[Y] ;
int k = diameter ;
for(int j = Y ; j!=-1 ; j = p[j])
k = min( k , max( d[j] , diameter-d[j] ) ) ;
radios.pb(k) ;
ans = max(ans , diameter) ;
}
sort(radios.begin() , radios.end()) ;
reverse(radios.begin() , radios.end() ) ;
if(radios.size()>=2)
ans = max( ans , radios[0] + radios[1] + L ) ;
if(radios.size() == 2) return ans ;
if(radios.size()>=3)
ans = max( ans , radios[1] + radios[2] + 2*L ) ;
return ans ;
}
/*int main()
{
int n , m , l , a[MAXN] , b[MAXN] , t[MAXN] ;
scanf("%d %d %d", &n, &m, &l) ;
lp(i,0,m) scanf("%d%d%d", &a[i] , &b[i] , &t[i]) ;
printf("%d\n",travelTime(n,m,l,a,b,t)) ;
}*/
