CodeEff/ECCO huggingface dataset:
# Original solution
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            ck = 0
            for ak, bk in zip(ai, bj):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
print((sum([sum(pk) % md for pk in pwr(a, k)]) % md))


# Optimized solution
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
print((sum([sum(pk) % md for pk in pwr(a, k)]) % md))
# Original solution
import sys
sys.setrecursionlimit(10**9)
N,K=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(N):
    A+=[list(map(int,input().strip().split(' ')))]
dic={}
MOD=10**9+7
def findout(i,j,k):
    
    if k==1:
        if A[i][j]==1:
            return 1
        else:
            return 0
    if (i,j,k) in dic:
        return dic[(i,j,k)]
    N=len(A)
    a1=k//2
    a2=k-a1
    
    ans=0
    for node in range(N):
        ans+=(findout(i,node,a1)*findout(node,j,a2))%MOD
    dic[(i,j,k)]=ans
    return ans
ans=0
for i in range(N):
    for j in range(N):
        ans+=findout(i,j,K)
        ans%=MOD
print(ans)

# Optimized solution
N,K=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(N):
    A+=[list(map(int,input().strip().split(' ')))]
dic={}
MOD=10**9+7
power=1
while 2**power<=K:
    power+=1

dp=[[[0 for j in range(N)] for i in range(N)] for p in range(power+1) ]
for p in range(0,power+1):
    
    if p==0:
        for i in range(N):
            for j in range(N):
                if A[i][j]==1:
                    dp[p][i][j]=1
    else:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[p][i][j]+=(dp[p-1][i][k]*dp[p-1][k][j])%MOD
                    dp[p][i][j]%=MOD

    
rep=bin(K)[2:][::-1]
final_ans=[[0 for i in range(N)] for j in range(N)]
need=[]
for i in range(len(rep)):
    if rep[i]=="1":
        need+=[i]

final=[[dp[need[0]][i][j] for j in range(N)] for i in range(N)]
for i in range(1,len(need)):
    ##start*dp[need[i]]
    temp_ans=[[0 for i in range(N)] for j in range(N)]
    for x in range(N):
        for y in range(N):
            temp=0
            for z in range(N):
                temp+=final[x][z]*dp[need[i]][z][y]
                temp%=MOD
            temp_ans[x][y]=temp
    final=[[temp_ans[i][j] for j in range(N)] for i in range(N)]
            
ans=0
for i in range(N):
    for j in range(N):
        ans+=final[i][j]
        ans%=MOD
print(ans)
# Original solution
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n,k = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(n)]
def calc(A,B):
  res = [[0]*n for i in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += A[i][k] * B[k][j]
      res[i][j] %= mod
  return res


def power(A,k):
  if k == 1:
    return A
  elif k % 2 == 0:
    tmp = power(A,k//2)
    return calc(tmp,tmp)
  elif k % 2 == 1:
    return calc(A,power(A,k-1))

result = power(A,k)
print((sum(map(sum,result))%mod))
    


# Optimized solution
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(n)]
def calc(A,B):
  res = [[0]*n for i in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += A[i][k] * B[k][j]
      res[i][j] %= mod
  return res


def power(A,k):
  if k == 1:
    return A
  elif k % 2 == 0:
    tmp = power(A,k//2)
    return calc(tmp,tmp)
  elif k % 2 == 1:
    return calc(A,power(A,k-1))

result = power(A,k)
print((sum(map(sum,result))%mod))
# Original solution
MOD = 10**9 + 7

def mul(a, b):
    return [
        [sum(aij * bij for aij, bij in zip(ai, bi)) % MOD for bi in zip(*b)]
        for ai in a]

def pow(b, k):
    if k == 1:
        return b
    i = 0
    while 2 ** (i + 1)<= k:
        i += 1

    k -= 2 ** i
    if k > 0:
        t = pow(b, k)
    for j in range(i):
        b = mul(b, b)
    if k > 0:
        b = mul(b, t)
    return b


def main():
    N, K = (int(i) for i in input().split())
    A = []
    for i in range(N):
        A.append([int(j) for j in input().split()])
    A = [i for i in zip(*A)]
    v = [[1] * N]
    return sum(mul(v, pow(A, K))[0]) % MOD

print((main()))


# Optimized solution
MOD = 10**9 + 7

def mul(a, b):
    return [
        [sum(aij * bij for aij, bij in zip(ai, bi)) % MOD for bi in zip(*b)]
        for ai in a]

def pow(b, k):
    r = [[1 if i == j else 0 for i in range(len(b))] for j in range(len(b))]
    while k:
        if k & 1:
            r = mul(r, b)
        k >>= 1
        b = mul(b, b)
    return r


def main():
    N, K = (int(i) for i in input().split())
    A = []
    for i in range(N):
        A.append([int(j) for j in input().split()])
    A = [i for i in zip(*A)]
    v = [[1] * N]
    return sum(mul(v, pow(A, K))[0]) % MOD

print((main()))
# Original solution
# coding: utf-8
# Your code here!
MOD=10**9+7

def dot(a, b):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k, aik in enumerate(a[i]):
            for j,bkj in enumerate(b[k]):
                res[i][j] += aik*bkj
                res[i][j] %= MOD
    return res


n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = [[0] * n for _ in range(n)]
for i in range(n):
    ans[i][i] = 1

while k:
    k, i = divmod(k, 2)
    if i:
        ans = dot(ans, A)
    A = dot(A, A)

res = 0
for i in range(n):
  for j in range(n):
    res += ans[i][j]
    res %= MOD
print(res)

# Optimized solution
# coding: utf-8
# Your code here!
MOD=10**9+7

def matmul(A, B, mod): # A,B: 行列
    res = [[0] * len(B[0]) for _ in range(len(A))]
    for i, resi in enumerate(res):
        for k, aik in enumerate(A[i]):
            for j,bkj in enumerate(B[k]):
                resi[j] += aik*bkj
                resi[j] %= mod
    return res

def matpow(A, p, M): #A^p mod M
    if p % 2 == 1:
        return matmul(A, matpow(A, p - 1, M), M)
    elif p > 0:
        b = matpow(A, p // 2, M)
        return matmul(b, b, M)
    else:
        return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]


n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = matpow(A,k,MOD)
print((sum(sum(r) % MOD for r in ans) % MOD))
# Original solution
# @author 

import sys

class RWalk:
    def solve(self):

        MOD = 10 ** 9 + 7

        def mult(A, B):
            n, m, p = len(A), len(A[0]), len(B[0])
            assert(len(B) == m)
            C = [[0] * p for _ in range(n)]
            for i in range(n):
                for j in range(p):
                    for k in range(m):
                        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD

            return C

        def pow(A, k):
            n, m = len(A), len(A[0])
            if k == 0:
                return [[1 if i == j else 0 for j in range(m)] for i in range(n)]

            if k % 2 == 0:
                return pow(mult(A, A), k // 2)

            return mult(A, pow(A, k - 1))


        n, k = [int(_) for _ in input().split()]
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])

        print((sum([sum(line) for line in pow(a, k)]) % MOD))

solver = RWalk()
input = sys.stdin.readline

solver.solve()


# Optimized solution
# @author 

import sys

class RWalk:
    def solve(self):

        MOD = 10 ** 9 + 7

        def mult(A, B):
            n, m, p = len(A), len(A[0]), len(B[0])
            assert(len(B) == m)
            C = [[0] * p for _ in range(n)]
            for i in range(n):
                for k in range(m):
                    a = A[i][k]
                    row = B[k]
                    for j in range(p):
                        C[i][j] = (C[i][j] + a * row[j]) % MOD

            return C

        def pow(A, k):
            n, m = len(A), len(A[0])
            if k == 0:
                return [[1 if i == j else 0 for j in range(m)] for i in range(n)]

            if k % 2 == 0:
                return pow(mult(A, A), k // 2)

            return mult(A, pow(A, k - 1))


        n, k = [int(_) for _ in input().split()]
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])

        print((sum([sum(line) for line in pow(a, k)]) % MOD))

solver = RWalk()
input = sys.stdin.readline

solver.solve()
# Original solution
N, K = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7


def dot(M1, M2, mod=10**9+7):
  n = len(M1)
  res = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += M1[i][k] * M2[k][j] % MOD
  
  return res


def power(M, k, mod=10**9+7):
  if k == 1:
    return M
  elif k%2 == 0:
    return power(dot(M, M, mod), k//2)
  else:
    return dot(M, power(dot(M, M, mod), k//2), mod)


trans = power(A, K) 

ans = 0
for t in trans:
  ans += sum(t)%MOD
  ans %= MOD

print(ans)

# Optimized solution
N, K = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7


def dot(M1, M2, mod=10**9+7):
  n = len(M1)
  res = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] = (res[i][j] + M1[i][k] * M2[k][j]) % MOD
  
  return res


def power(M, k, mod=10**9+7):
  if k == 1:
    return M
  elif k%2 == 0:
    return power(dot(M, M, mod), k//2, mod)
  else:
    return dot(M, power(dot(M, M, mod), k//2), mod)


trans = power(A, K) 

ans = 0
for t in trans:
  ans += sum(t)%MOD
  ans %= MOD

print(ans)
# Original solution
import sys
sys.setrecursionlimit(10 ** 6)

def main():
    N, Q = list(map(int, input().split()))

    G = []
    for i in range(N):
        G.append([False] * N)

    for i in range(N-1):
        a, b = list(map(int, input().split()))
        G[a-1][b-1] = True
        G[b-1][a-1] = True

    c = [0] * N
    for i in range(Q):
        p, x = list(map(int, input().split()))
        c[p-1] += x

    visited = [False] * N

    def dfs(v, d):
        if visited[v]:
            return
        c[v] += d

        visited[v] = True
        val = c[v]
        for i, n in enumerate(G[v]):
            if n:
                dfs(i, val)

    dfs(0, 0)
    print((" ".join([str(i) for i in c])))


if __name__ == "__main__":
    main()

# Optimized solution
import sys
sys.setrecursionlimit(10 ** 6)

def main():
    N, Q = list(map(int, input().split()))

    G = []
    for i in range(N):
        G.append([])

    for i in range(N-1):
        a, b = list(map(int, input().split()))
        # G[a-1][b-1] = True
        # G[b-1][a-1] = True
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    c = [0] * N
    for i in range(Q):
        p, x = list(map(int, input().split()))
        c[p-1] += x

    visited = [False] * N

    def dfs(v, d):
        if visited[v]:
            return
        c[v] += d
        visited[v] = True
        val = c[v]
        for child in G[v]:
            dfs(child, val)

    dfs(0, 0)
    print((" ".join([str(i) for i in c])))


if __name__ == "__main__":
    main()
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5 * 2)

N, Q = list(map(int, input().split()))
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1,N+1)}

for _ in range(Q):
    p, x = list(map(int, input().split()))
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)

propagate(1, 0)

print((' '.join(str(C[i]) for i in range(1,N+1))))


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = list(map(int, input().split()))
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1,N+1)}

for _ in range(Q):
    p, x = list(map(int, input().split()))
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)

propagate(1, 0)

print((' '.join(str(C[i]) for i in range(1,N+1))))
# Original solution
import copy
n,q=list(map(int,input().split()))
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print((' '.join(distance)))

# Optimized solution
n,q=list(map(int,input().split()))
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
 
L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=L3
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print((' '.join(distance)))
# Original solution
n,q=list(map(int,input().split()))
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
 
L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=L3
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print((' '.join(distance)))

# Optimized solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
 
L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=L3
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print((' '.join(distance)))
# Original solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
 
L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=L3
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print((' '.join(distance)))

# Optimized solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[]
for i in range(n):
  connection.append([])
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
 
L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=L3
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print((' '.join(distance)))
# Original solution
n,q=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

L=[list(map(int,input().split())) for i in range(q)]
ctL=[0]*n
for i in range(q):
  ctL[L[i][0]-1]+=L[i][1]

def bfs(v):
  distance=[-1]*n
  distance[v]=ctL[v]
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=distance[next[i]]+ctL[connection[next[i]][j]]
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(0)
for i in range(n):
  x[i]=str(x[i])
print((' '.join(x)))

# Optimized solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

L=[list(map(int,input().split())) for i in range(q)]
ctL=[0]*n
for i in range(q):
  ctL[L[i][0]-1]+=L[i][1]

def bfs(v):
  distance=[-1]*n
  distance[v]=ctL[v]
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=distance[next[i]]+ctL[connection[next[i]][j]]
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(0)
for i in range(n):
  x[i]=str(x[i])
print((' '.join(x)))
# Original solution
import sys
sys.setrecursionlimit(10 ** 7)

N,Q = list(map(int,input().split()))
AB = [[int(i) for i in input().split()] for _ in range(N-1)]
PX = [[int(j) for j in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
counters = [0] * (N+1)
for p,x in PX:
    counters[p] += x
    
def dfs(v,parent,add):
    counters[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,counters[v])

dfs(1,0,0)

ans = ' '.join(map(str,counters[1:]))
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = list(map(int,input().split()))
AB = [[int(i) for i in input().split()] for _ in range(N-1)]
PX = [[int(j) for j in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
counters = [0] * (N+1)
for p,x in PX:
    counters[p] += x
    
def dfs(v,parent,add):
    counters[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,counters[v])

dfs(1,0,0)

ans = ' '.join(map(str,counters[1:]))
print(ans)
# Original solution
n,q=list(map(int,input().split()))
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

temp=[[i+1] for i in range(n)]
for i in range(n-2,-1,-1):
    if len(temp[ab[i][1]-1]) >= 2:
        temp[ab[i][0]-1].extend(temp[ab[i][1]-1])
    else:
        temp[ab[i][0]-1].append(ab[i][1]) 


ans=[0 for i in range(n)]
for j in range(q):
    for _ in temp[px[j][0]-1]:
        ans[_-1]+=px[j][1]

print((" ".join(map(str,ans))))

# Optimized solution
n,q=list(map(int,input().split()))
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

parent=[0 for i in range(n)]
for i in range(n-1):
    parent[ab[i][1]-1]=ab[i][0]
ans=[0 for i in range(n)]
for i in range(q):
    ans[px[i][0]-1]+=px[i][1]
for i in range(1,n):
    if parent[i] != 0:
        ans[i]+=ans[parent[i]-1]


print((" ".join(map(str,ans))))