#include "dreaming.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ll n, m, l;

vector<ii> Adj[N];

vector<ll> lens, nodes;

ll d[N];
bool vis[N];

void dfs(ll u, ll p){
	vis[u] = 1;
	nodes.pb(u);
	for(auto it : Adj[u]){
		ll v = it.fi;
		if(v == p) continue;
		d[v] = d[u] + it.se;
		dfs(v, u);
	}
}

bool find(ll u, ll p, ll node){
	if(u == node) return 1;
	for(auto it : Adj[u]){
		ll v = it.fi, w = it.se;
		if(v == p) continue;
		bool temp = find(v, u, node);
		if(temp){
			lens.pb(w);
			return 1;
		}
	}
	return 0;
}

ll rt[N], sz[N], mx_dep[N];
ll rtt[N], szz[N], mx_d[N];

ll root(ll x){
	return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

//ll mx = -1;

set<ii> comps, ori;

void merge(ll x, ll y){
	x = root(x), y = root(y);
	if(x == y) return;
	if(sz[x] < sz[y]) swap(x, y);
	rt[y] = x;
	sz[x] += sz[y];
	comps.erase({mx_dep[x], x});
	comps.erase({mx_dep[y], y});
	mx_dep[x] = max(min(mx_dep[x], mx_dep[y]) + l, max(mx_dep[x], mx_dep[y]));
	comps.insert({mx_dep[x], x});
}

bool ck(ll x){
	for(ll i = 0; i < n; i++){
		rt[i] = rtt[i], sz[i] = szz[i], mx_dep[i] = mx_d[i];
	}
	comps.clear();
	comps = ori;
	while(comps.size() > 1){
		set<ii>::iterator it = comps.end();
		it--;
		ii a = (*it);
		it--;
		ii b = (*it);
	//	cout << x << " " << a.fi << " " << b.fi << "\n";
		if(a.fi > x) return 0;
		if(a.fi + b.fi + l > x) return 0;
		if(a.fi + b.fi + 2 * l <= x) return 1;
		merge(a.se, b.se);
	}
	set<ii>::iterator it = comps.end();
	it--;
	ii a = (*it);
	if(a.fi > x) return 0;
	return 1;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	n = N, m = M, l = L;
	for(ll i = 0; i < m; i++){
		Adj[A[i]].pb({B[i], T[i]});
		Adj[B[i]].pb({A[i], T[i]});
	}
	ll mxx = -1;
	for(ll i = 0; i < n; i++){
		if(vis[i]) continue;
		nodes.clear();
		d[i] = 0;
		dfs(i, i);
		ii mx = {-1, -1};
		for(auto it : nodes){
			rtt[it] = it, szz[it] = nodes.size();
			mx = max(mx, {d[it], it});
		}
		d[mx.se] = 0;
		dfs(mx.se, mx.se);
		ii mx2 = {-1, -1};
		for(auto it : nodes) mx2 = max(mx2, {d[it], it});
		mxx = max(mxx, mx2.fi);
		lens.clear();
		find(mx.se, mx.se, mx2.se);
		ll mini = oo, sum = 0;
		for(auto it : lens) sum += it;
		ll sum2 = 0;
		mini = sum;
		for(auto it : lens){
	//		cout << it << "\n";
			sum -= it;
			sum2 += it;
			mini = min(mini, max(sum, sum2));
		}
		mx_d[i] = mini;
	//	cout << i << " " << mx_d[i] << "\n";
		ori.insert({mx_d[i], i});
	}
	ll l = mxx, r = 2e9;
	while(l < r){
		ll mid = (l + r) >> 1;
		if(!ck(mid)) l = mid + 1;
		else r = mid;
	}
	return (int)l;
}