#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int n, m, d1;
vector <vector <pair <int, int>>> adj;
vector <int> v;
vector <bool> visited;
vector <int> d;
vector <int> diameter;
int mx, mxd;
int answer;
void bfs( int i ) {
queue <int> q;
q.push( i );
v.push_back( i );
visited[i] = true;
while ( !q.empty() ) {
int x = q.front();
q.pop();
for ( auto y : adj[x] ) {
if ( visited[y.first] == false ) {
visited[y.first] = true;
q.push( y.first );
}
}
}
return;
}
int median( int i ) {
int answer1;
int start, end, dist;
queue <int> q;
q.push( i );
d[i] = 0;
start = i;
vector <int> w;
while ( !q.empty() ) {
int x = q.front();
q.pop();
w.push_back( x );
for ( auto y : adj[x] ) {
if ( d[y.first] == -1 ) {
d[y.first] = d[x] + y.second;
q.push( y.first );
}
}
if ( d[x] > d[start] ) {
start = x;
}
}
end = start;
for ( auto x : w ) {
d[x] = -1;
}
d[start] = 0;
diameter[start] = start;
q.push( start );
while ( !q.empty() ) {
int x = q.front();
q.pop();
for ( auto y : adj[x] ) {
if ( d[y.first] == -1 ) {
diameter[y.first] = x;
d[y.first] = d[x] + y.second;
q.push( y.first );
}
}
if ( d[x] > d[end] ) {
end = x;
}
}
dist = 0;
answer1 = d[end];
mxd = max( mxd, d[end] );
while ( end != start ) {
answer1 = min( answer1, max( dist, d[end] ) );
dist += d[end] - d[diameter[end]];
end = diameter[end];
}
return answer1;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, d1 = L;
visited.resize( n, false );
adj.resize( n );
d.resize( n, -1 );
diameter.resize( n );
for ( int i = 0; i < m; i++ ) {
adj[A[i]].push_back( { B[i], T[i] } );
adj[B[i]].push_back( { A[i], T[i] } );
}
for ( int i = 0; i < n; i++ ) {
if ( visited[i] == false ) {
bfs( i );
}
}
vector <int> medians;
for ( int i = 0; i < (int)v.size(); i++ ) {
medians.push_back( median( v[i] ) );
}
sort ( medians.rbegin(), medians.rend() );
answer = mxd;
if ( medians.size() > 1 ) {
answer = max( answer, medians[0] + medians[1] + d1 );
}
if ( medians.size() > 2 ) {
answer = max( answer, medians[1] + medians[2] + d1 + d1 );
}
return answer;
}
/*
#include <stdio.h>
#include <stdlib.h>
//#include "dreaming.h"
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
int N, M, L, i;
int res;
FILE *f = fopen("dreaming.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
fclose(f);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
*/
