#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, int>> g[200001];
vector<pair<int, int>>minP(200001);
int n, LN;
int timer;
vector<int> level;
vector<vector<int>> dp;

void dfs1(int u, int p) {
	level[u] = level[p] + 1;
	dp[u][0] = p;
	for (int i = 1; i < LN; ++i)
		dp[u][i] = dp[dp[u][i - 1]][i - 1];
	for (int i = 0; i < g[u].size(); ++i) {
		auto v = g[u][i];
		if (v.first == p) continue;
		dfs1(v.first, u);
	}
}

int lca(int u, int v) {
	if (level[u] < level[v])
		swap(u, v);
	int diff = level[u] - level[v];
	for (int i = 0; i < LN; ++i) {
		if ((1 << i) & diff)
			u = dp[u][i];
	}
	if (u == v)
		return u;
	for (int i = LN - 1; i >= 0; --i) {
		if (dp[u][i] != dp[v][i]) {
			u = dp[u][i];
			v = dp[v][i];
		}
	}
	return dp[u][0];
}

pair<int, int> towfive(int w)
{
	int notwo = 0;
	int nofive = 0;
	while (w % 2 == 0)
	{
		notwo++;
		w /= 2;
	}
	while (w % 5 == 0)
	{
		nofive++;
		w /= 5;
	}
	return {notwo, nofive};
}
void dfs(int i, int p, int no2, int no5)
{
	minP[i].first = no2;
	minP[i].second = no5;
	//cout << i << " " << no2 << " " << no5 << "\n";
	for (auto it : g[i])
	{
		if (it.first == p)
		{
			continue;
		}
		int w1 = it.second;
		int node = it.first;
		pair<int, int> x = towfive(w1);
		dfs(node, i, x.first + no2, x.second + no5);
	}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int n, q;
	cin >> n >> q;
	for (int i = 1; i < n; i++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		g[x].push_back({y, w});
		g[y].push_back({x, w});
	}
	level.resize(n + 1);
	timer = 0;
	LN = ceil(log2(n + 1));
	dp.assign(n + 1, vector<int>(LN + 1));
	dfs(1, 0, 0, 0);
	dfs1(1, 0);
	cout << "\n";
	for (int i = 0; i < q; i++)
	{
		int x, y;
		cin >> x >> y;
		int ans1 = minP[x].first + minP[y].first - 2 * minP[lca(x, y)].first;
		int ans2 = minP[x].second + minP[y].second - 2 * minP[lca(x, y)].second;
		int ans = min(ans1, ans2);
		cout << ans << "\n";
	}
	return 0;
}

``