公元 2044 年，人类进入了宇宙纪元。

L 国有 n 个星球，还有 n?1 条双向航道，每条航道建立在两个星球之间，这 n?1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 tj，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？

输出文件只包含一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5

11

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
 
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
    if(Head == Tail) {
        int l = fread(buffer, 1, BufferSize, stdin);
        Tail = (Head = buffer) + l;
    }
    return *Head++;
}
int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
    return x * f;
}

#define maxn 300010
#define maxm 600010
#define maxlog 20
#define oo 2147483647
int n, m, q, head[maxn], next[maxm], to[maxm], dist[maxm];
struct Que {
	int a, b, d;
	Que() {}
	Que(int _1, int _2, int _3): a(_1), b(_2), d(_3) {}
	bool operator < (const Que& t) const { return d > t.d; }
} qs[maxn];

void AddEdge(int a, int b, int c) {
	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
	swap(a, b);
	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
	return ;
}

int dep[maxn], Dep[maxn], fa[maxlog][maxn], mx[maxlog][maxn], L[maxn], R[maxn], clo, list[maxm], cl, pos[maxn];
void build(int u) {
	L[u] = ++clo; list[++cl] = u; pos[u] = cl;
	for(int i = 1; i < maxlog; i++) {
		int v = fa[i-1][u];
		fa[i][u] = fa[i-1][v];
		mx[i][u] = max(mx[i-1][u], mx[i-1][v]);
	}
	for(int e = head[u]; e; e = next[e]) if(to[e] != fa[0][u]) {
		fa[0][to[e]] = u;
		mx[0][to[e]] = dist[e];
		dep[to[e]] = dep[u] + 1;
		Dep[to[e]] = Dep[u] + dist[e];
		build(to[e]);
		list[++cl] = u;
	}
	R[u] = clo;
	return ;
}
int Log[maxm], Lca[maxlog][maxm];
void rmq_init() {
	Log[1] = 0;
	for(int i = 2; i <= cl; i++) Log[i] = Log[i>>1] + 1;
	for(int i = 1; i <= cl; i++) Lca[0][i] = list[i];
	for(int j = 1; (1 << j) <= cl; j++)
		for(int i = 1; i + (1 << j) - 1 <= cl; i++) {
			int a = Lca[j-1][i], b = Lca[j-1][i+(1<<j-1)];
			Lca[j][i] = dep[a] < dep[b] ? a : b;
		}
	return ;
}
int lca(int a, int b) {
	int l = min(pos[a], pos[b]), r = max(pos[a], pos[b]), t = Log[r-l+1];
	a = Lca[t][l]; b = Lca[t][r-(1<<t)+1];
	return dep[a] < dep[b] ? a : b;
}
int calc(int a, int b) {
	return Dep[a] + Dep[b] - (Dep[lca(a,b)] << 1);
}
int calcmx(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	int Mx = 0;
	for(int i = maxlog-1; i >= 0; i--) if(dep[a] - (1 << i) >= dep[b])
		Mx = max(Mx, mx[i][a]), a = fa[i][a];
	for(int i = maxlog-1; i >= 0; i--) if(fa[i][a] != fa[i][b])
		Mx = max(Mx, max(mx[i][a], mx[i][b])),
		a = fa[i][a], b = fa[i][b];
	return a == b ? Mx : max(Mx, max(mx[0][a], mx[0][b]));
}

bool cmp(int a, int b) { return dep[a] > dep[b]; }
bool isson(int pa, int son) { return L[pa] <= L[son] && L[son] <= R[pa]; }

int main() {
	n = read(); q = read();
	for(int i = 1; i < n; i++) {
		int a = read(), b = read(), c = read();
		AddEdge(a, b, c);
	}
	build(1); rmq_init();
	for(int i = 1; i <= q; i++) {
		int u = read(), v = read();
		qs[i] = Que(u, v, calc(u, v));
	}
	sort(qs + 1, qs + q + 1);
//	for(int i = 1; i <= q; i++) printf("%d %d %d %d\n", qs[i].a, qs[i].b, qs[i].d, lca(qs[i].a, qs[i].b));
	int A = qs[1].a, B = qs[1].b, ans = oo;
//	printf("%d %d(%d %d)\n", qs[2].d, calcmx(A, B), A, B);
	if(qs[1].d != qs[2].d || q == 1)
		ans = min(ans, max(qs[2].d, qs[1].d - calcmx(A, B)));
	for(int i = 2; i <= q; i++) {
		int a = qs[i].a, b = qs[i].b, C = lca(A, B);
		int ps[10];
		ps[1] = lca(a, A); ps[2] = lca(a, B); ps[3] = lca(a, b);
		ps[4] = lca(b, A); ps[5] = lca(b, B); ps[6] = lca(A, B);
		sort(ps + 1, ps + 7, cmp);
		int cp = unique(ps + 1, ps + 7) - ps;
		A = ps[1]; B = ps[2];
		bool ok = 1;
		for(int j = 3; j <= cp; j++)
			if(!isson(ps[j], A) || !isson(ps[j], B)) {
				ok = 0; break;
			}
		if(!ok) break;
		if(qs[i].d != qs[i+1].d || i == q)
			ans = min(ans, max(qs[i+1].d, qs[1].d - calcmx(A, B)));
//		printf("[%d %d]\n", A, B);
	}
	
	printf("%d\n", ans);
	
	return 0;
}