#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


vector<int> solve(vector<pair<int, int>> r, vector<ll> d, vector<int> s, vector<int> t, vector<bool> l)
{
    int n = r.size()+1;
    int m = d.size();
    vector<int> ans(m);
    vector<vector<int>> g(n);
    for (auto [a, b] : r)
    {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    vector<vector<int>> pth(m);
    for (int i = 0; i < m; i++)
    {
        vector<int> dst(n, 10000000);
        dst[s[i]] = 0;
        queue<int> q;
        q.push(s[i]);

        while (!q.empty())
        {
            int v = q.front(); q.pop();
            for (int u : g[v]) if (dst[u] > n)
            {
                dst[u] = dst[v]+1;
                q.push(u);
            }
        }

        int v = t[i];
        while (dst[v] != 0)
        {
            pth[i].push_back(v);
            for (int u : g[v]) if (dst[u] < dst[v])
            {
                v = u;
                break;
            }
        }
        pth[i].push_back(s[i]);
    }


    map<int, vector<int>> ev;
    for (int i = 0; i < m; i++) ev[d[i]].push_back(i);

    while (!ev.empty())
    {
        auto p = *ev.begin();
        ev.erase(ev.begin());

        unordered_set<int> inf;
        for (int x : p.second) if (l[x]) if (!pth[x].empty()) inf.insert(pth[x].back());
        for (int x : p.second) 
        {   
            if (inf.count(pth[x].back())) l[x] = true;
            if (l[x]) ans[x]++;
            pth[x].pop_back();
            if (!pth[x].empty()) ev[p.first+1].push_back(x);    
        }
    }

    return ans;
}










// signed main() {
//     int n, m;

//     std::cin >> n;
//     std::cin >> m;

//     std::vector<std::pair<int, int>> edges = {};
//     std::vector<long long> day;
//     std::vector<int> start;
//     std::vector<int> target;
//     std::vector<bool> infected;

//     for (int i = 0; i < n - 1; i++) {
//         int u, v;
//         std::cin >> u >> v;
//         edges.emplace_back(u, v);
//     }

//     for (int i = 0; i < m; i++) {
//         long long _d, _s, _t, _i;
//         std::cin >> _d >> _s >> _t >> _i;
//         day.push_back(_d);
//         start.push_back(_s);
//         target.push_back(_t);
//         infected.push_back(_i);
//     }

//     const auto ans = solve(edges, day, start, target, infected);
//     for (const auto it : ans) {
//         std::cout << it << std::endl;
//     }

//     return 0;
// }
