#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define int int // 是否开 long long
typedef long long ll;
typedef int itn; // 个人防手滑
typedef int tin; // 个人防手滑
typedef int nti; // 个人防手滑
const int inf = 0x3f3f3f3f;
inline int read(){ // 快读 int
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline long long readll(){ // 快读 long long
	long long x=0,f=1;
    char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c&15);c=getchar();}
	return x*f;
}
void write(int x){ // 快写
    if(x<0){x=-x;putchar(45);}
    if(x>9) write(x/10);
    putchar(x%10+48);
    return;
}
const int maxn = 100010;
const ll mod = 1e9;
int n, m, tot, cnt, mn, root;
ll ans;
struct sbt{
    int siz, ch[2], val;
}t[20000005];
vector<int> ch[maxn];
int r[maxn], f[19][maxn], siz[maxn], dep[maxn], head[maxn], next[maxn << 1], to[maxn << 1], vis[maxn], p[maxn];
int r1[maxn], r2[maxn], fa[maxn], dd[maxn], Log[maxn];
queue<int> q;
int mem;
void pushup(int x) { t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + 1; }
void rotate(int &x, int d){
    int y = t[x].ch[d];
    t[x].ch[d] = t[y].ch[d ^ 1], t[y].ch[d ^ 1] = x;
    pushup(x), pushup(y), x = y;
}
void maintain(int &x, int d){
    if(t[t[t[x].ch[d]].ch[d]].siz > t[t[x].ch[d ^ 1]].siz) rotate(x, d);
    else if(t[t[t[x].ch[d]].ch[d ^ 1]].siz > t[t[x].ch[d ^ 1]].siz) rotate(t[x].ch[d], d ^ 1), rotate(x, d);
    else return;
    maintain(t[x].ch[0], 0), maintain(t[x].ch[1], 1);
    maintain(x, 0), maintain(x, 1);
}
void insert(int &x, int y){
    if (!x){
        mem--;
        x = q.front(), q.pop();
        t[x].siz = 1, t[x].val = y, t[x].ch[0] = t[x].ch[1] = 0;
        return;
    }
    int d = (y >= t[x].val);
    t[x].siz++, insert(t[x].ch[d], y);
    maintain(x, d);
}
int query(int x, int y){
    if(!x)
        return 0;
    if (t[x].val <= y)
        return query(t[x].ch[1], y) + 1 + t[t[x].ch[0]].siz;
    return query(t[x].ch[0], y);
}
void del(int &x)
{
    if (!x)
        return;
    mem++;
    del(t[x].ch[0]), del(t[x].ch[1]), t[x].siz = t[x].val = 0, q.push(x), x = 0;
}
void getrt(int x, int fa)
{
    siz[x] = 1;
    int i, tmp = 0;
    for (i = head[x]; i != -1; i = next[i])
        if (to[i] != fa && vis[to[i]] == 2)
            getrt(to[i], x), siz[x] += siz[to[i]], tmp = max(tmp, siz[to[i]]);
    tmp = max(tmp, tot - siz[x]);
    if (tmp < mn)
        mn = tmp, root = x;
}
void solve(int x)
{
    vis[x] = 1;
    for (int i = head[x]; i != -1; i = next[i])
        if (vis[to[i]] == 2)
            tot = siz[to[i]], mn = 1 << 30, getrt(to[i], x), fa[root] = x, solve(root);
}
void add(int a, int b)
{
    to[cnt] = b, next[cnt] = head[a], head[a] = cnt++;
}
int lca(int a, int b)
{
    if (dd[a] < dd[b])
        swap(a, b);
    int i;
    for (i = Log[dd[a] - dd[b]]; i >= 0; i--)
        if (dd[f[i][a]] >= dd[b])
            a = f[i][a];
    if (a == b)
        return b;
    for (i = Log[dd[a]]; i >= 0; i--)
        if (f[i][a] != f[i][b])
            a = f[i][a], b = f[i][b];
    return f[0][a];
}
int dis(int a, int b)
{
    return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
int main()
{
    read(), n = read();
    memset(head, -1, sizeof(head));
    int a, b, u, last, flast;
    mem = 20000000;
    for(int i = 1; i <= 20000000; i++) q.push(i);
    read(), read(), r[1] = read(), siz[1] = 1, dd[1] = 1, ch[1].push_back(1), insert(r1[1], -r[1]);
    for(int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1;
    printf("0\n");
    for (int i = 2; i <= n; i++){
        a = read() ^ (ans % mod), b = read(), r[i] = read();
        add(a, i), add(i, a), dep[i] = dep[a] + b, dd[i] = dd[a] + 1;
        f[0][i] = a, fa[i] = a;
        for(int j = 1; j <= Log[dd[i]]; j++) f[j][i] = f[j - 1][f[j - 1][i]];
        for (last = 0, u = i; u; u = fa[u]){
            ans += query(r1[u], r[i] - dis(i, u));
            ch[u].push_back(i), insert(r1[u], dis(i, u) - r[i]), siz[u]++;
            if (fa[u]){
                ans -= query(r2[u], r[i] - dis(i, fa[u]));
                insert(r2[u], dis(i, fa[u]) - r[i]);
            }
            if (fa[u] && siz[u] * 1.0 > (siz[fa[u]] + 1) * 0.88) last = fa[u];
        }
        if (last){
            flast = fa[last], vis[flast] = 3;
            int j;
            for (j = 0, p[0] = 0; j < (int)ch[last].size(); j++)
                p[++p[0]] = ch[last][j];
            for (j = 1; j <= p[0]; j++)
                ch[p[j]].clear(), del(r1[p[j]]), del(r2[p[j]]), vis[p[j]] = 2;
            tot = p[0], mn = 1 << 30, getrt(last, 0), fa[root] = flast, solve(root);
            for(j = 1; j <= p[0]; j++){
                for(u = p[j]; u != flast; u = fa[u]){
                    ch[u].push_back(p[j]);
                    insert(r1[u], dis(p[j], u) - r[p[j]]);
                    if(fa[u]) insert(r2[u], dis(p[j], fa[u]) - r[p[j]]);
                }
            }
        }
        cout << ans;
    }
    return 0;
}