#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

const int N = 1e5 + 7;

int n, l;
vector<pair<int, int>> g[N];
int dpdown[N], dpup[N];
bool used[N];
vector<int> comp;
int par[N];

void dfsdown(int v) {
	used[v] = 1;
	dpdown[v] = 0;
	comp.push_back(v);
	for (auto [u, w] : g[v]) {
		if (!used[u]) {
			par[u] = v;
			dfsdown(u);
			dpdown[v] = max(dpdown[v], dpdown[u] + w);
		}
	}
}

void dfsup(int v) {
	used[v] = 1;
	multiset<int> st = {0};
	if (par[v] != -1) {
		st.insert(dpup[v]);
	}
	for (auto [u, w] : g[v]) {
		if (u != par[v]) {
			st.insert(dpdown[u] + w);
		}
	}
	for (auto [u, w] : g[v]) {
		if (u != par[v]) {
			st.erase(st.find(dpdown[u] + w));
			assert(!st.empty());
			dpup[u] = *st.rbegin() + w;
			dfsup(u);
			st.insert(dpdown[u] + w);
		}
	}
}

bool check(int x, vector<int> d) {
	while (d.size() >= 2) {
		int a = d.back();
		d.pop_back();
		int b = d.back();
		d.pop_back();
		if (a + b + l > x) {
			return 0;
		}
		if (a + b + 2 * l <= x) {
			break;
		}
		d.push_back(max(a, b + l));
	}
	return 1;
}

}

int travelTime(int grdn, int grdm, int grdl, int grda[], int grdb[], int grdt[]) {
	n = grdn;
	l = grdl;
	for (int i = 0; i < grdm; ++i) {
		int a = grda[i], b = grdb[i];
		int t = grdt[i];
		g[a].push_back({b, t});
		g[b].push_back({a, t});
	}
	vector<int> d;
	int diam = 0;
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			comp.clear();
			par[i] = -1;
			dfsdown(i);
			for (int v : comp) {
				used[v] = 0;
			}
			dfsup(i);
			int mn = 1e9;
			for (int v : comp) {
				int mx = dpdown[v];
				if (par[v] != -1) {
					mx = max(mx, dpup[v]);
				}
				diam = max(diam, mx);
				mn = min(mn, mx);
			}
			d.push_back(mn);
		}
	}
	sort(d.begin(), d.end());
	int lb = diam - 1, rb = 1e9;
	while (rb - lb > 1) {
		int mb = (lb + rb) / 2;
		if (check(mb, d)) {
			rb = mb;
		} else {
			lb = mb;
		}
 	}
 	return rb;
}