You are given a tree (a connected undirected graph without cycles) of $n$ vertices. Each of the $n - 1$ edges of the tree is colored in either black or red.

You are also given an integer $k$. Consider sequences of $k$ vertices. Let's call a sequence $[a_1, a_2, \ldots, a_k]$ good if it satisfies the following criterion:  We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from $a_1$ and ending at $a_k$.  Start at $a_1$, then go to $a_2$ using the shortest path between $a_1$ and $a_2$, then go to $a_3$ in a similar way, and so on, until you travel the shortest path between $a_{k-1}$ and $a_k$. If you walked over at least one black edge during this process, then the sequence is good.  [Image] 

Consider the tree on the picture. If $k=3$ then the following sequences are good: $[1, 4, 7]$, $[5, 5, 3]$ and $[2, 3, 7]$. The following sequences are not good: $[1, 4, 6]$, $[5, 5, 5]$, $[3, 7, 3]$.

There are $n^k$ sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo $10^9+7$.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $2 \le k \le 100$), the size of the tree and the length of the vertex sequence.

Each of the next $n - 1$ lines contains three integers $u_i$, $v_i$ and $x_i$ ($1 \le u_i, v_i \le n$, $x_i \in \{0, 1\}$), where $u_i$ and $v_i$ denote the endpoints of the corresponding edge and $x_i$ is the color of this edge ($0$ denotes red edge and $1$ denotes black edge).


-----Output-----

Print the number of good sequences modulo $10^9 + 7$.


-----Examples-----
Input
4 4
1 2 1
2 3 1
3 4 1

Output
252
Input
4 6
1 2 0
1 3 0
1 4 0

Output
0
Input
3 5
1 2 1
2 3 0

Output
210


-----Note-----

In the first example, all sequences ($4^4$) of length $4$ except the following are good:   $[1, 1, 1, 1]$ $[2, 2, 2, 2]$ $[3, 3, 3, 3]$ $[4, 4, 4, 4]$ 

In the second example, all edges are red, hence there aren't any good sequences.

Source: codeforces | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Tree algorithms

Mathematics

Spanning trees


Solutions:
def dfs(x, p):
	vertex = 1
	vis[x] = True
	for i in graph[x].keys():
		if not vis[i]:
			vertex += dfs(i, x)
	return vertex
(n, k) = map(int, input().split())
answer = pow(n, k)
vis = [False for _ in range(n + 1)]
graph = [{} for _ in range(n + 1)]
dark_edges = 0
for _ in range(1, n):
	(u, v, x) = map(int, input().split())
	if not x:
		graph[u][v] = x
		graph[v][u] = x
	else:
		dark_edges += 1
temp = 0
if dark_edges:
	for i in range(1, n + 1):
		if not vis[i]:
			temp += pow(dfs(i, -1), k)
	print((pow(n, k) - temp) % (pow(10, 9) + 7))
else:
	print(0)


from collections import Counter
modulo = 10 ** 9 + 7

def pow(a, n):
	res = 1
	while n:
		if n & 1:
			res *= a
			res %= modulo
		a *= a
		a %= modulo
		n //= 2
	return res
(n, k) = map(int, input().split())
links = [[i] for i in range(n)]

def mark(a):
	res = links[a - 1]
	while type(res[0]) == list:
		res = res[0]
	if type(links[a - 1][0]) == list:
		links[a - 1][:] = [res]
	return res
for _ in range(n - 1):
	(a, b, t) = map(int, input().split())
	if not t:
		ma = mark(a)
		mb = mark(b)
		if ma != mb:
			mb[:] = [ma]
res = pow(n, k)
for v in Counter((mark(x)[0] for x in range(1, n + 1))).values():
	res -= pow(v, k)
	res %= modulo
print(res)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def dfs(d, visit, s):
	q = [s]
	cnt = 0
	while q:
		t = q.pop(0)
		visit[t] = True
		cnt += 1
		for x in d[t]:
			if visit[x] == False:
				q.insert(0, x)
	return cnt

def mod(a, b, c):
	res = a * b
	return res % c

def power(a, b, m):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = mod(x, y, m)
		y = mod(y, y, m)
		b >>= 1
	return x

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def main():
	try:
		(n, k) = In()
		d = defaultdict(list)
		for i in range(n - 1):
			(a, b, c) = In()
			if c == 0:
				d[a].append(b)
				d[b].append(a)
		ans = power(n, k, P)
		visit = [False for x in range(n + 1)]
		for i in range(1, n + 1):
			if not visit[i]:
				ans -= power(dfs(d, visit, i), k, P)
		print(ans % P)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


from collections import deque as dq, defaultdict as dd
mod = 1000000007

def power(x, y):
	ans = 1
	while y:
		if y % 2:
			ans = ans % mod * (x % mod) % mod
		y = y >> 1
		x = x % mod * (x % mod) % mod
	return ans
(n, k) = map(int, input().split())
d = dd(list)
for i in range(n - 1):
	(u, v, a) = map(int, input().split())
	if a == 0:
		d[u].append(v)
		d[v].append(u)
vis = [0] * (n + 1)
cl = 0
for i in range(1, n + 1):
	if vis[i] == 0:
		q = [i]
		q = dq(q)
		cou = 0
		while q:
			cou += 1
			a = q.pop()
			vis[a] = 1
			for j in d[a]:
				if vis[j] == 0:
					q.appendleft(j)
		b = power(cou, k)
		cl = (cl % mod + b % mod) % mod
print((power(n, k) - cl + 1000000007) % mod)


import sys
input = sys.stdin.readline
from collections import defaultdict
(n, k) = map(int, input().split())
g = defaultdict(list)
for _ in range(n - 1):
	(u, v, x) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	if not x:
		g[u].append(v)
		g[v].append(u)
MOD = 10 ** 9 + 7
res = pow(n, k, MOD)
visited = [False for _ in range(n)]
for i in range(n):
	if not visited[i]:
		cnt = 1
		visited[i] = True
		stack = [i]
		while stack:
			curr = stack.pop()
			for ne in g[curr]:
				if not visited[ne]:
					visited[ne] = True
					cnt += 1
					stack.append(ne)
		res -= pow(cnt, k, MOD)
print(res % MOD)


def bfs(start):
	global count
	queue = []
	queue.append(start)
	visited[start] = True
	count += 1
	while queue:
		start = queue.pop(0)
		for i in range(len(adj[start])):
			ele = adj[start][i]
			if not visited[ele]:
				visited[ele] = True
				count += 1
				queue.append(ele)
(n, k) = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
visited = [False] * n
ca = []
for i in range(n):
	if not visited[i]:
		count = 0
		bfs(i)
		ca.append(count)
ans = 0
mod = 10 ** 9 + 7
pa = pow(n, k, mod)
for i in ca:
	ans = (ans + pow(i, k, mod)) % mod
print((pa - ans) % mod)


def dfs(s):
	(stk, cnt) = ([], [])
	stk.append(s)
	cnt.append(0)
	while len(stk) > 0:
		s = stk[-1]
		ll = cnt[-1]
		visit[s] = 1
		flag = 1
		for j in range(ll, len(adj[s]), 1):
			if visit[adj[s][j]] == 0:
				ct[0] += 1
				cnt[-1] = j + 1
				stk.append(adj[s][j])
				cnt.append(0)
				flag = 0
				break
		if flag:
			stk.pop()
			cnt.pop()

def power(a, b, mod):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % mod
		a = a * a % mod
		b >>= 1
	return res
(n, k) = map(int, input().split())
adj = [0] * (n + 1)
for i in range(n + 1):
	adj[i] = []
for i in range(n - 1):
	(x, y, f) = map(int, input().split())
	if f == 0:
		adj[x].append(y)
		adj[y].append(x)
visit = [0] * (n + 1)
mp = {}
for i in range(1, n + 1):
	if visit[i] == 0:
		ct = [1] * 1
		dfs(i)
		mp[i] = ct[0]
ans = power(n, k, 1000000007)
for i in mp:
	ans = (ans - power(mp[i], k, 1000000007) + 1000000007) % 1000000007
print(ans)


def dfs(edges, visited, node):
	red = 0
	if node not in visited:
		for kid in edges[node]:
			if kid[1] == 0 and kid[0] not in visited:
				red += 1
				break
	stack = [node]
	while stack:
		curr = stack.pop()
		if curr not in visited:
			found = False
			visited.add(curr)
			for kid in edges[curr]:
				if kid[1] == 0 and kid[0] not in visited:
					stack.append(kid[0])
					red += 1
	return red

def solve(edges, k):
	mod = 10 ** 9 + 7
	n = len(edges)
	total = pow(n, k, mod)
	remove = 0
	visited = set()
	for i in range(1, n + 1):
		if i not in visited:
			red = dfs(edges, visited, i)
			remove += pow(red, k, mod)
			remove -= red
			remove = remove % mod
	remove += n
	remove = remove % mod
	print((total - remove) % mod)

def main():
	(n, k) = map(int, input().split())
	edges = {}
	for i in range(1, n + 1):
		edges[i] = []
	for i in range(n - 1):
		(u, v, x) = map(int, input().split())
		edges[u].append((v, x))
		edges[v].append((u, x))
	solve(edges, k)
main()


def find_set(v):
	if v == parent[v]:
		return v
	else:
		parent[v] = find_set(parent[v])
		return parent[v]

def union_sets(a, b):
	a = find_set(a)
	b = find_set(b)
	if a != b:
		if rank[a] < rank[b]:
			(a, b) = (b, a)
		parent[b] = a
		if rank[a] == rank[b]:
			rank[a] += 1
(n, k) = list(map(int, input().split()))
parent = [i for i in range(n)]
rank = [0] * n
for i in range(n - 1):
	(a, b, c) = list(map(int, input().split()))
	if c == 0:
		union_sets(a - 1, b - 1)
a = {}
for i in range(n):
	if find_set(i) not in a:
		a[find_set(i)] = 1
	else:
		a[find_set(i)] += 1
s = 0
m = 10 ** 9 + 7
for i in a:
	s = (s + pow(a[i], k, m)) % m
print((pow(n, k, m) - s) % m)


import sys
sys.setrecursionlimit(10 ** 5 + 10)
(n, k) = map(int, input().split())
parents = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]

def find(a):
	if a == parents[a]:
		return a
	parents[a] = find(parents[a])
	return parents[a]

def union(a, b):
	a = find(a)
	b = find(b)
	if a != b:
		if size[a] < size[b]:
			(a, b) = (b, a)
		parents[b] = a
		size[a] += size[b]

def same(a, b):
	return find(a) == find(b)
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		union(a, b)
dictionary = {}
for i in range(1, n + 1):
	f = find(i)
	if f not in dictionary:
		dictionary[f] = 0
	dictionary[f] += 1
s = n ** k
for key in dictionary:
	s -= dictionary[key] ** k
print(s % (10 ** 9 + 7))


from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
md = 10 ** 9 + 7
(n, k) = map(int, input().split())
cnt_e = 0
graph = [[] for i in range(n + 1)]
for _ in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		cnt_e += 1
		graph[u].append(v)
		graph[v].append(u)
total = pow(n, k, md)
if cnt_e == n:
	print(0)
	exit()
visited = [False] * (n + 1)
b = 0
for i in range(1, n + 1):
	if visited[i]:
		continue
	queue = deque()
	queue.append(i)
	visited[i] = True
	cnt = 0
	while queue:
		el = queue.pop()
		for node in graph[el]:
			if visited[node]:
				continue
			visited[node] = True
			queue.append(node)
		cnt += 1
	b += pow(cnt, k, md)
print((total + md - b) % md)


mod = 10 ** 9 + 7
import sys
input = sys.stdin.buffer.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root, vis):
		queue = [root]
		queue = deque(queue)
		c = 0
		while len(queue) != 0:
			element = queue.popleft()
			c += 1
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
		return c

	def dfs(self, root, ans):
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i != self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def ifcycle(self):
		self.bfs(0)
		queue = [0]
		vis = [0] * n
		queue = deque(queue)
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in graph[element]:
				if vis[i] == 1 and i != parent[element]:
					return True
				if vis[i] == 0:
					queue.append(i)
					vis[i] = 1
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue
(n, k) = map(int, input().split())
g = Graph(n, False)
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if not c:
		g.addEdge(a - 1, b - 1)
vis = [0] * n
count = 0
for i in range(n):
	if not vis[i]:
		c = g.bfs(i, vis)
		count += pow(c, k, mod)
		count %= mod
print((pow(n, k, mod) - count) % mod)


import sys
input = sys.stdin.readline

class disjoint:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]
		self.size = [1] * n

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		xid = self.find(x)
		yid = self.find(y)
		if xid == yid:
			return
		if self.rank[xid] < self.rank[yid]:
			self.parent[xid] = yid
			self.size[yid] += self.size[xid]
			return
		elif self.rank[xid] > self.rank[yid]:
			self.parent[yid] = xid
			self.size[xid] += self.size[yid]
			return
		else:
			self.parent[yid] = xid
			self.rank[xid] += 1
			self.size[xid] += self.size[yid]
			return
from collections import *
pri = pow(10, 9) + 7
(n, k) = map(int, input().split())
obj = disjoint(n + 1)
for i in range(n - 1):
	(x, y, z) = map(int, input().split())
	if z == 0:
		obj.union(x, y)
al = defaultdict(int)
total = 0
for i in range(1, n + 1):
	if al[obj.find(i)] == 0:
		m = obj.size[obj.find(i)]
		total += pow(m, k, pri)
		al[obj.find(i)] = 1
print((pow(n, k, pri) - total) % pri)


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)

def find(x):
	if x != par[x]:
		par[x] = find(par[x])
	return par[x]
(n, k) = mdata()
par = [i for i in range(n + 1)]
for i in range(n - 1):
	(u, v, x) = mdata()
	if x == 0:
		par[find(par[u])] = find(par[v])
d = dd(int)
for i in range(1, n + 1):
	d[find(par[i])] += 1
ans = pow(n, k, mod)
for i in d:
	ans -= pow(d[i], k, mod)
print((ans + mod) % mod)


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
from bisect import bisect, bisect_left
import math
from itertools import permutations
import queue
tot = 0

def dfs(arr, start):
	global tot
	global visited
	if visited[start - 1]:
		return
	visited[start - 1] = True
	tot += 1
	for child in arr[start]:
		if not visited[child - 1]:
			dfs(arr, child)
I = stdin.readline
(n, k) = map(int, I().split())
blacks = dict()
arr = defaultdict(lambda : [])
for i in range(n - 1):
	(a, b, c) = map(int, I().split())
	if c == 0:
		arr[a].append(b)
		arr[b].append(a)
	else:
		blacks[a] = 1
		blacks[b] = 1
lengts = []
visited = [False for i in range(n)]
for i in blacks.keys():
	tot = 0
	dfs(arr, i)
	lengts.append(tot)
if len(blacks.keys()) == 0:
	print(0)
else:
	mod = 10 ** 9 + 7
	ans = pow(n, k, mod)
	for i in lengts:
		ans -= pow(i, k, mod)
		ans += mod
		ans %= mod
	print(ans)


from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

def dfs(u):
	st = [u]
	id = u
	while st:
		u = st.pop()
		if cv[u]:
			continue
		cv[u] = 1
		count[id] += 1
		for (nxt, w) in adj[u]:
			if w == 1:
				continue
			st.append(nxt)
(n, k) = [int(item) for item in input().split()]
adj = defaultdict(list)
vs = []
for i in range(n - 1):
	(u, v, w) = [int(item) for item in input().split()]
	adj[u].append([v, w])
	adj[v].append([u, w])
	if w == 1:
		vs.append([u, v])
count = {key: 0 for key in range(1, n + 1)}
cv = [0] * (n + 1)
ccs = []
for i in range(1, n + 1):
	if not cv[i]:
		dfs(i)
		ccs.append(count[i])
ans = pow(n, k, MOD)
for x in ccs:
	ans = (ans - pow(x, k, MOD) + MOD) % MOD
print(ans)


import collections

class UnionFind:

	def __init__(self, n):
		self._id = list(range(n))
		self._sz = [1] * n

	def _root(self, i):
		j = i
		while j != self._id[j]:
			self._id[j] = self._id[self._id[j]]
			j = self._id[j]
		return j

	def find(self, p, q):
		return self._root(p) == self._root(q)

	def union(self, p, q):
		i = self._root(p)
		j = self._root(q)
		if i == j:
			return
		if self._sz[i] < self._sz[j]:
			self._id[i] = j
			self._sz[j] += self._sz[i]
		else:
			self._id[j] = i
			self._sz[i] += self._sz[j]
(n, k) = map(int, input().split())
uf = UnionFind(n)
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	u -= 1
	v -= 1
	if x == 0:
		uf.union(u, v)
d = collections.defaultdict(int)
for i in range(n):
	d[uf._root(i)] += 1
total = pow(n, k, 10 ** 9 + 7)
for size in d.values():
	total -= pow(size, k, 10 ** 9 + 7)
total %= 10 ** 9 + 7
print(total)


from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

def BFC(digraph, v, oboid):
	s2 = set()
	s1 = set()
	s1.add(v)
	cnt = 0
	while s1 != set():
		for element in s1:
			if element not in oboid:
				oboid.add(element)
				cnt += 1
				for key in digraph[element]:
					s2.add(key)
		s1 = s2
		s2 = set()
	return cnt
(n, k) = map(int, input().split())
MOD = 10 ** 9 + 7
graph = {i: set() for i in range(1, n + 1)}
D = []
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		graph[u].add(v)
		graph[v].add(u)
wo = len(graph)
oboid = set()
comps = 0
ansq = 0
for v in graph:
	if v not in oboid:
		cnt = BFC(graph, v, oboid)
		ansq += pow(cnt, k, MOD)
		ansq %= MOD
print((pow(n, k, MOD) - ansq) % MOD)


(n, k) = map(int, input().split(' '))
smej = []
seen = []
ans = n ** k

def bfs(t):
	global c, ocher
	if seen[t] is False:
		seen[t] = True
		ocher.pop(0)
		c += 1
		for s in smej[t]:
			if seen[s] is False and s not in ocher:
				ocher.append(s)
	else:
		ocher.pop(0)
for t in range(n):
	smej.append([])
	seen.append(False)
for q in range(n - 1):
	(u, v, x) = map(int, input().split(' '))
	if x == 1:
		continue
	else:
		smej[u - 1].append(v - 1)
		smej[v - 1].append(u - 1)
for e in range(n):
	c = 0
	ocher = [e]
	while len(ocher) != 0:
		bfs(ocher[0])
	ans -= c ** k
print(ans % (10 ** 9 + 7))


(n, k) = map(int, input().split())
gr = [None] * (n + 1)
vis = [False] * (n + 1)
cnt = 0

def dfs(i):
	global vis, cnt
	l = [i]
	size = 1
	while size > 0:
		i = l[size - 1]
		vis[i] = True
		l.pop()
		size -= 1
		for x in gr[i]:
			if vis[x] == False:
				l.append(x)
				size += 1
		cnt += 1
for i in range(n + 1):
	gr[i] = []
for i in range(1, n):
	(x, y, w) = map(int, input().split())
	if w == 0:
		gr[x].append(y)
		gr[y].append(x)
ans = pow(n, k, 1000000007)
for i in range(1, n + 1):
	if vis[i] == False:
		cnt = 0
		dfs(i)
		ans -= pow(cnt, k, 1000000007)
print(ans % 1000000007)


import sys
(n, k) = list(map(int, sys.stdin.readline().split()))
sc = 0
d = dict()
los = []
for i in range(n - 1):
	(u, v, x) = list(map(int, sys.stdin.readline().split()))
	if not x:
		if u not in d and v not in d:
			d[u] = sc
			d[v] = sc
			los += [{u, v}]
			sc += 1
		elif u in d and v not in d:
			d[v] = d[u]
			los[d[u]].add(v)
		elif u not in d and v in d:
			d[u] = d[v]
			los[d[v]].add(u)
		elif u in d and v in d:
			stc = d[v]
			los[d[u]] |= los[d[v]]
			for j in los[stc]:
				d[j] = d[u]
			los[stc] = set()
colos = []
for s in los:
	if s:
		colos += [len(s)]
if sum(colos) < n:
	colos += [1] * (n - sum(colos))
cs = n ** k
for s in colos:
	cs -= s ** k
print(cs % 1000000007)


def parser():
	while 1:
		data = list(input().split(' '))
		for number in data:
			if len(number) > 0:
				yield number
input_parser = parser()

def get_word():
	global input_parser
	return next(input_parser)

def get_number():
	data = get_word()
	try:
		return int(data)
	except ValueError:
		return float(data)

def calc(pa, pb, a, b):
	p = max(pa, pb)
	n = min(a, b)
	if pa == pb and n - p > 0:
		return n - p
	elif not pa == pb and n - p >= 0:
		return 1 + n - p
	else:
		return 0

class Elem:

	def __init__(self, data):
		self.data = data
		self.parent = self
		self.size = 1

	def merge(self, toElem):
		toParent = toElem.getParent()
		myParent = self.getParent()
		myParent.parent = toParent
		toParent.size += myParent.size
		myParent.size = toParent.size

	def getParent(self):
		if self == self.parent:
			return self
		else:
			return self.parent.getParent()
n = get_number()
k = get_number()
elems = []
for i in range(n):
	elems.append(Elem(i + 1))
for i in range(n - 1):
	u = get_number()
	v = get_number()
	x = get_number()
	if x == 0:
		elems[u - 1].merge(elems[v - 1])
groups = []
for i in elems:
	if i.getParent().data == i.data:
		groups.append([i.data, i.size])
bad = 0
for i in groups:
	bad += i[1] ** k
result = n ** k
m = 1000000007
print((result - bad) % m)


def findCC(temp, queue):
	while queue:
		node = queue.pop(0)
		if visited[node] == False:
			temp.append(node)
			visited[node] = True
			for adj in edgeList[node]:
				if visited[adj] == False:
					queue.append(adj)
	return temp
(n, k) = map(int, input().split())
MOD = 1000000007
edgeList = dict()
for i in range(n):
	edgeList[i] = []
for _ in range(n - 1):
	(u, v, c) = map(int, input().split())
	if c == 0:
		edgeList[u - 1].append(v - 1)
		edgeList[v - 1].append(u - 1)
visited = [False for i in range(n)]
cc = []
for i in range(n):
	if visited[i] == False:
		temp = []
		queue = [i]
		cc.append(findCC(temp, queue))
		visited[i] = True
noOfCC = len(cc)
totalAns = pow(n, k, MOD)
for i in range(noOfCC):
	ni = len(cc[i])
	totalAns = (totalAns - pow(ni, k, MOD)) % MOD
print(totalAns)


(n, k) = map(int, input().split())
dsu = [-1 for i in range(n)]
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	u -= 1
	v -= 1
	if x == 0:
		(upath, vpath) = ([], [])
		while dsu[u] >= 0:
			upath.append(u)
			u = dsu[u]
		while dsu[v] >= 0:
			vpath.append(v)
			v = dsu[v]
		if u == v:
			lol = 0
		elif -dsu[u] > -dsu[v]:
			vpath.append(v)
			dsu[u] += dsu[v]
			v = u
		else:
			upath.append(u)
			dsu[v] += dsu[u]
			u = v
		for x in upath:
			dsu[x] = u
		for x in vpath:
			dsu[x] = v
sum = n ** k
for a in dsu:
	if a < 0:
		sum -= (-a) ** k
print(sum % 1000000007)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
M = 10 ** 9 + 7

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def solve():
	(N, K) = getInts()
	graph = col.defaultdict(set)
	nodes = set([j + 1 for j in range(N)])
	for n in range(N - 1):
		(U, V, X) = getInts()
		if not X:
			graph[U].add(V)
			graph[V].add(U)
	ans = pow(N, K, M)

	@bootstrap
	def dfs(node):
		if node in nodes:
			nodes.remove(node)
			visited.append(node)
		for neighbour in graph[node]:
			if neighbour in nodes:
				yield dfs(neighbour)
		yield
	while nodes:
		node = next(iter(nodes))
		visited = []
		dfs(node)
		ans -= pow(len(visited), K, M)
	return ans % M
print(solve())


kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, k) = kk()
dsud = {i: {i} for i in range(n)}
dsup = {i: i for i in range(n)}
for _ in range(n - 1):
	(u, v, xi) = kk()
	(u, v) = (u - 1, v - 1)
	if xi == 0:
		(s1, s2) = (dsud[dsup[u]], dsud[dsup[v]])
		if len(s1) > len(s2):
			s1 |= s2
			del dsud[dsup[v]]
			for el in s2:
				dsup[el] = dsup[u]
		else:
			s2 |= s1
			del dsud[dsup[u]]
			for el in s1:
				dsup[el] = dsup[v]
val = 0
for se in dsud:
	val += len(dsud[se]) ** k
print((n ** k - val) % (7 + 10 ** 9))


import sys
MOD = 10 ** 9 + 7

class UnionFind:

	def __init__(self, n):
		self.par = [-1 for i in range(n + 1)]

	def root(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		if self.par[x] > self.par[y]:
			(x, y) = (y, x)
		self.par[x] += self.par[y]
		self.par[y] = x

	def issame(self, x, y):
		return self.root(x) == self.root(y)

	def size(self, x):
		return -self.par[self.root(x)]
(n, k) = map(int, sys.stdin.readline().rstrip().split())
Tree = UnionFind(n)
for i in range(n - 1):
	(u, v, x) = map(int, sys.stdin.readline().rstrip().split())
	if x == 0:
		Tree.union(u - 1, v - 1)
ans = pow(n, k, MOD)
for i in range(n):
	if Tree.root(i) == i:
		ans -= pow(Tree.size(i), k, MOD)
print(ans % MOD)


import sys
import math
from collections import defaultdict, deque
import heapq
mod = 10 ** 9 + 7

def find(node, parent):
	while parent[node] != node:
		node = parent[node]
	return node

def union(u, v, parent, child):
	paru = find(u, parent)
	parv = find(v, parent)
	if child[paru] > child[parv]:
		child[paru] += child[parv]
		child[parv] = 0
		parent[parv] = paru
	else:
		child[parv] += child[paru]
		child[paru] = 0
		parent[paru] = parv
(n, k) = map(int, sys.stdin.readline().split())
child = [1 for _ in range(n + 1)]
parent = [i for i in range(n + 1)]
edges = []
for i in range(n - 1):
	(u, v, w) = map(int, sys.stdin.readline().split())
	edges.append([u, v, w])
	if w == 0:
		union(u, v, parent, child)
ans = pow(n, k, mod)
for i in range(1, n + 1):
	ans -= pow(child[i], k, mod)
	ans %= mod
print(ans % mod)


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
import threading
threading.stack_size(67108864)

def main():
	(n, k) = map(int, input().split())
	uw = []
	ubw = []
	for i in range(n):
		uw.append([])
		ubw.append([])
	for i in range(n - 1):
		(a, b, v) = map(int, input().split())
		ubw[a - 1].append(b - 1)
		ubw[b - 1].append(a - 1)
		if v == 0:
			uw[a - 1].append(b - 1)
			uw[b - 1].append(a - 1)

	def dfs(v):
		use[v] = 1
		com[c] += 1
		for i in uw[v]:
			if not use[i]:
				dfs(i)
	use = [0] * n
	c = 0
	com = []
	for i in range(n):
		if not use[i]:
			com.append(0)
			dfs(i)
			c += 1
	q = 10 ** 9 + 7
	ans = pow(n, k, q)
	for i in range(c):
		ans -= pow(com[i], k, q)
		ans %= q
	print(ans)
thread = threading.Thread(target=main)
thread.start()
thread.join()


mod = 10 ** 9 + 7

def dfs(v, vis):
	cnt = 1
	st = []
	st.append(v)
	while st:
		x = st.pop()
		for i in g[x]:
			if vis[i[0]] == 0 and i[1] == 0:
				vis[i[0]] = 1
				cnt += 1
				st.append(i[0])
	return cnt
(n, k) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(n - 1):
	(x, y, z) = map(int, input().split())
	x -= 1
	y -= 1
	g[x].append([y, z])
	g[y].append([x, z])
vis = [0] * n
res = pow(n, k, mod)
for i in range(n):
	if vis[i] == 0:
		vis[i] = 1
		tmp = dfs(i, vis)
		res = (res % mod - pow(tmp, k, mod)) % mod
print(res)


from collections import deque
mod = 10 ** 9 + 7

class TreeNode:

	def __init__(self, val):
		self.val = val
		self.edges = {}

	def add_edge(self, node, color):
		self.edges[node] = color
(n, k) = map(int, input().split())
tree = []
for i in range(1, n + 1):
	tree.append(TreeNode(i))
for _ in range(n - 1):
	(u, v, x) = map(int, input().split())
	tree[u - 1].add_edge(v, x)
	tree[v - 1].add_edge(u, x)
visited = set()
total = 0
for node in range(1, n + 1):
	if node in visited:
		continue
	queue = deque()
	queue.append(node)
	visited.add(node)
	red_vertexes = 1
	while queue:
		vertex = queue.popleft()
		for (e, c) in tree[vertex - 1].edges.items():
			if c == 0 and e not in visited:
				queue.append(e)
				red_vertexes = red_vertexes + 1
				visited.add(e)
	total = (total + pow(red_vertexes, k, mod)) % mod
total = (pow(n, k, mod) - total) % mod
print(total)


import collections
from collections import defaultdict
(n, k) = input().split()
(n, k) = [int(n), int(k)]
graph1 = defaultdict(list)
power = n ** k % (10 ** 9 + 7)
for x in range(n - 1):
	(u, v, x) = input().split()
	(u, v, x) = [int(u), int(v), int(x)]
	if x == 0:
		graph1[u].append(v)
		graph1[v].append(u)

def bfs(graph, root):
	count = 1
	queue = collections.deque([root])
	visited.add(root)
	while queue:
		vertex = queue.popleft()
		for neighbour in graph[vertex]:
			if neighbour not in visited:
				visited.add(neighbour)
				queue.append(neighbour)
				count += 1
	return count
visited = set()
for i in range(1, n + 1):
	if i not in visited:
		xy = bfs(graph1, i)
		power = (power - xy ** k % (10 ** 9 + 7)) % (10 ** 9 + 7)
print(power % (10 ** 9 + 7))


(n, k) = map(int, input().split())
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		g[u].append(v)
		g[v].append(u)
MOD = 10 ** 9 + 7
vis = [0] * (n + 1)
ans = pow(n, k)
for i in range(1, n + 1):
	if vis[i] == 0:
		cnt = 0
		stack = [i]
		while stack:
			u = stack.pop()
			if vis[u]:
				continue
			vis[u] = 1
			cnt += 1
			for v in g[u]:
				if not vis[v]:
					stack.append(v)
		ans -= pow(cnt, k)
print(ans % MOD)


from collections import defaultdict
for _ in range(1):
	(n, k) = map(int, input().split())
	graph = defaultdict(list)
	present = 0
	for i in range(n - 1):
		(u, v, color) = map(int, input().split())
		if color == 1:
			present = 1
		else:
			graph[u].append(v)
			graph[v].append(u)
	if not present:
		print(0)
	else:
		visited = [0 for _ in range(n + 1)]
		ans = pow(n, k, 1000000007)
		left = n
		for node in range(1, n + 1):
			if node not in graph:
				continue
			if not visited[node]:
				stack = [node]
				visited[node] = 1
				count = 1
				while stack:
					cn = stack[-1]
					stack.pop()
					for nn in graph[cn]:
						if not visited[nn]:
							stack.append(nn)
							visited[nn] = 1
							count += 1
				ans -= pow(count, k, 1000000007)
				left -= count
		print((ans - left) % 1000000007)


class UnionFind(object):

	def __init__(self, n):
		self.root = [i for i in range(n)]
		self.size = [1 for _ in range(n)]

	def find(self, x):
		if self.root[x] == x:
			return x
		self.root[x] = self.find(self.root[x])
		return self.root[x]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.root[y] = x
		self.size[x] += self.size[y]

def pow_mod(a, b, p):
	ret = 1
	while b > 0:
		if b % 2 == 1:
			ret = ret * a % p
		b //= 2
		a = a * a % p
	return ret

def main():
	(n, k) = map(int, input().split())
	union_find = UnionFind(n + 1)
	for _ in range(n - 1):
		(u, v, c) = map(int, input().split())
		if c == 0:
			union_find.union(u, v)
	p = int(1000000000.0 + 7)
	ret = pow_mod(n, k, p)
	used = set()
	for i in range(1, n + 1):
		x = union_find.find(i)
		if x not in used:
			ret = (ret + p - pow_mod(union_find.size[x], k, p)) % p
			used.add(x)
	print(ret)
main()


class UnionFind:

	def __init__(self, n):
		self.follow = [-1] * (n + 1)
		self.num_follower = [1] * (n + 1)

	def root_index_of(self, a):
		r = a
		while self.follow[r] > -1:
			r = self.follow[r]
		return r

	def connected(self, a, b):
		return self.root_index_of(a) == self.root_index_of(b)

	def connect(self, a, b):
		ra = self.root_index_of(a)
		rb = self.root_index_of(b)
		if ra == rb:
			return
		if self.num_follower[ra] < self.num_follower[rb]:
			self.follow[ra] = rb
			self.follow[a] = rb
			self.num_follower[rb] += self.num_follower[ra]
		else:
			self.follow[rb] = ra
			self.follow[b] = ra
			self.num_follower[ra] += self.num_follower[rb]
mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
b = 0
r = 0
uf = UnionFind(n)
for _ in range(n - 1):
	(u, v, color) = map(int, input().split())
	if color:
		b += 1
	else:
		uf.connect(u, v)
		r += 1
if b == 0:
	print(0)
	exit()
s = set()
cnt = 0
for i in range(1, n + 1):
	root = uf.root_index_of(i)
	num = uf.num_follower[root]
	if root in s:
		continue
	else:
		s.add(root)
		cnt += pow(num, k, mod)
ans = pow(n, k, mod)
ans -= cnt
print(ans % mod)


def find(x):
	if par[x] == x:
		return x
	par[x] = find(par[x])
	return par[x]

def union(a, x):
	xa = find(a)
	xb = find(b)
	if xa != xb:
		if size[xa] > size[xb]:
			(xa, xb) = (xb, xa)
		size[xb] += size[xa]
		size[xa] = 1
		par[xa] = par[xb]
(n, k) = map(int, input().split())
par = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]
visited = [0 for i in range(n + 1)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		visited[a] = 1
		visited[b] = 1
		union(a, b)
f_ans = n ** k
count = 0
ans = 0
for i in range(1, n + 1):
	ans += size[i] ** k if size[i] > 1 else 0
	if visited[i] == 0:
		count += 1
print((f_ans - ans - count) % (10 ** 9 + 7))


def find(v):
	if parent[v] == v:
		return v
	parent[v] = find(parent[v])
	return parent[v]

def union(u, v):
	(root_u, root_v) = (find(u), find(v))
	if cnt[root_v] > cnt[root_u]:
		(root_u, root_v) = (root_v, root_u)
	parent[root_v] = root_u
	cnt[root_u] += cnt[root_v]
(n, k) = map(int, input().split())
parent = [v for v in range(n + 1)]
cnt = [1 for _ in range(n + 1)]
for _ in range(1, n):
	(u, v, x) = map(int, input().split())
	if x == 1:
		continue
	union(u, v)
mod = 10 ** 9 + 7
answer = n ** k % mod
for v in range(1, n + 1):
	if parent[v] == v:
		val = cnt[v] ** k % mod
		answer = (answer - val) % mod
print(answer)


(n, k) = map(int, input().split())
G = []
p = [i for i in range(n + 1)]
h = [0 for i in range(n + 1)]
r = [1 for i in range(n + 1)]

def get(x):
	while p[x] != x:
		x = p[x]
	return x

def union(x, y):
	x = get(x)
	y = get(y)
	if x == y:
		return 0
	if h[x] > h[y]:
		(x, y) = (y, x)
	p[x] = y
	if h[x] == h[y]:
		h[y] += 1
	r[y] += r[x]
	return 1
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		union(u, v)
for i in range(1, n + 1):
	if i == p[i]:
		G.append(r[i])
ans = 0
for x in G:
	ans += pow(x, k, 10 ** 9 + 7)
ans = (pow(n, k, 10 ** 9 + 7) - ans) % (10 ** 9 + 7)
print(ans)


(n, k) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	g[u - 1].append((v - 1, x))
	g[v - 1].append((u - 1, x))
v = [0 for i in range(n)]
comps = []
for i in range(n):
	if v[i] == 1:
		continue
	v[i] = 1
	comps.append([i])
	q = [i]
	while q:
		u0 = q[0]
		q = q[1:]
		for (u, x) in g[u0]:
			if x == 0 and v[u] == 0:
				q.append(u)
				v[u] = 1
				comps[-1].append(u)
ans = n ** k
for comp in comps:
	ans -= len(comp) ** k
print(ans % (10 ** 9 + 7))


def powmod(n, k, m):
	if n == 1:
		return 1
	expow = n
	for i in range(1, k):
		expow = expow * n % m
	return expow
(n, k) = (int(x) for x in input().rstrip().split())
rededges = {i: [] for i in range(1, n + 1)}
for i in range(n - 1):
	(ui, vi, xi) = (int(x) for x in input().rstrip().split())
	if xi == 0:
		rededges[ui].append(vi)
		rededges[vi].append(ui)
notvisited = {i for i in range(1, n + 1)}
compdims = []
while notvisited:
	x = notvisited.pop()
	tovisit = rededges[x]
	compdim = 1
	while tovisit:
		compdim += len(tovisit)
		nbrs = tovisit[:]
		tovisit = []
		for y in nbrs:
			notvisited.remove(y)
			tovisit += [z for z in rededges[y] if z in notvisited]
	compdims.append(compdim)
m = 10 ** 9 + 7
goodpaths = powmod(n, k, m)
for cd in compdims:
	goodpaths -= powmod(cd, k, m)
goodpaths = goodpaths % m
print(goodpaths)


mod = 10 ** 9 + 7
(n, k) = [int(i) for i in input().split(' ')]
root = [i for i in range(n + 1)]
num = [1] * (n + 1)

def findroot(x):
	if root[x] == x:
		return x
	else:
		root[x] = findroot(root[x])
		return root[x]

def union(x, y):
	xroot = findroot(x)
	yroot = findroot(y)
	if num[xroot] >= num[yroot]:
		num[xroot] += num[yroot]
		root[yroot] = xroot
	else:
		num[yroot] += num[xroot]
		root[xroot] = yroot
for i in range(n - 1):
	(u, v, x) = [int(s) for s in input().split(' ')]
	if x == 0:
		union(u, v)
ans = n ** k
for i in range(1, n + 1):
	if i == root[i]:
		ans -= num[i] ** k
print(ans % mod)


from collections import deque

def bfs(graph, visited, node):
	size = 0
	q = deque()
	q.appendleft(node)
	while len(q) > 0:
		n = q.pop()
		visited[n] = True
		size += 1
		for neighbor in graph[n]:
			if not visited[neighbor]:
				q.appendleft(neighbor)
	return size
(n, k) = map(int, input().split())
total = n ** k
graph = [[] for x in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
visited = [False for x in range(n)]
for i in range(n):
	if not visited[i]:
		s = bfs(graph, visited, i)
		total -= s ** k
print(total % (10 ** 9 + 7))


_MOD = 10 ** 9 + 7
from collections import defaultdict
(n, k) = map(int, input().split())
g = defaultdict(dict)
for _ in range(n - 1):
	(u, v, x) = map(int, input().split())
	g[u][v] = g[v][u] = x
visited_vertex = set()
groups = []
for i in range(1, n + 1):
	if i in visited_vertex:
		continue
	s = [i]
	visited_vertex.add(i)
	group = {i}
	while len(s) > 0:
		e = s.pop()
		for next in g[e]:
			if next in visited_vertex or g[e][next] == 1:
				continue
			s.append(next)
			visited_vertex.add(next)
			group.add(next)
	groups.append(group)
r = n ** k
for group in groups:
	r -= len(group) ** k
print(r % _MOD)


import sys
from collections import defaultdict, deque
input = lambda : sys.stdin.readline().strip('\r\n')
MOD = 10 ** 9 + 7

def BFS(v):
	visited[v] = True
	queue = deque()
	queue.append(v)
	cnt = 1
	while queue:
		curr = queue.popleft()
		for i in g[curr]:
			if not visited[i]:
				visited[i] = True
				queue.append(i)
				cnt += 1
	return cnt

def addEdges(edges, u, v):
	edges[v].append(u)
	edges[u].append(v)
(n, k) = map(int, input().split())
g = defaultdict(list)
for _ in range(n - 1):
	(x, y, c) = map(int, input().split())
	if not c:
		addEdges(g, x, y)
visited = [False] * (n + 1)
ans = pow(n, k, MOD)
for i in range(1, n + 1):
	if not visited[i]:
		val = BFS(i)
		ans = (ans - pow(val, k, MOD)) % MOD
print(ans % MOD)


class UnionFind:

	def __init__(self, n):
		self.par = [int(i) for i in range(n)]
		self.rank = [1] * (n + 1)
		self.rank[0] = 0

	def union(self, x, y):
		if not self.same_set(x, y):
			par_x = self.find(x)
			par_y = self.find(y)
			if self.rank[par_x] > self.rank[par_y]:
				self.rank[par_x] += self.rank[par_y]
				self.rank[par_y] = 0
				self.par[par_y] = par_x
			else:
				self.rank[par_y] += self.rank[par_x]
				self.rank[par_x] = 0
				self.par[par_x] = par_y
			self.find(x)
			self.find(y)

	def find(self, x):
		if self.par[x] == x:
			return x
		self.par[x] = self.find(self.par[x])
		return self.par[x]

	def same_set(self, x, y):
		return self.find(x) == self.find(y)

def fast_pow(x, y):
	if y == 1:
		return x
	if y % 2 != 0:
		return x % M * (fast_pow(x, y - 1) % M) % M
	aux = fast_pow(x, y / 2)
	return aux % M * (aux % M) % M
M = 1000000007
(n, k) = map(int, input().split())
max_pos = fast_pow(n, k)
uf = UnionFind(n + 1)
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		uf.union(u, v)
nao_bons = 0
for i in range(n + 1):
	if uf.rank[i] > 0:
		nao_bons = (nao_bons % M + fast_pow(uf.rank[i], k) % M) % M
print((max_pos % M - nao_bons % M) % M)


def factorial(n):
	if n == 0:
		return 1
	else:
		return n * factorial(n - 1) % (10 ** 9 + 7)
(n, k) = [int(i) for i in input().split()]
s = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = [int(i) for i in input().split()]
	if c == 0:
		s[a - 1].append(b - 1)
		s[b - 1].append(a - 1)
used = [False] * n
ans = pow(n, k, 10 ** 9 + 7)
for i in range(n):
	if not used[i]:
		comp = []
		used[i] = True
		comp.append(i)
		c = 0
		while c < len(comp):
			for h in s[comp[c]]:
				if not used[h]:
					used[h] = True
					comp.append(h)
			c += 1
		ans = (ans - pow(len(comp), k, 10 ** 9 + 7)) % (10 ** 9 + 7)
print(ans)


MOD = 1000000007
(N, K) = [int(s) for s in input().split(' ')]
edges = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = [int(s) for s in input().split(' ')]
	a -= 1
	b -= 1
	if c == 0:
		edges[a].append(b)
		edges[b].append(a)
ans = pow(N, K, MOD)
visited = [False for i in range(N)]

def dfs(i):
	ret = 0
	todo = [i]
	while len(todo) > 0:
		v = todo.pop()
		if visited[v]:
			continue
		ret += 1
		visited[v] = True
		for j in edges[v]:
			todo.append(j)
	return ret
for i in range(N):
	num = dfs(i)
	ans = (ans - pow(num, K, MOD) + MOD) % MOD
print(ans)


def readLine():
	a = input()
	return [int(i) for i in a.split(' ')]

def deg(x, y):
	if y == 1:
		return x
	res = deg(x, y // 2)
	res *= res
	res %= md
	if y % 2 == 1:
		res *= x
		res %= md
	return res

def bfs(v):
	q = [v]
	used[v] = True
	res = 1
	while len(q) != 0:
		v = q[0]
		q.pop(0)
		for (_, to) in enumerate(g[v]):
			if used[to] == False:
				used[to] = True
				q.append(to)
				res += 1
	return res
nm = readLine()
(n, m) = (nm[0], nm[1])
g = [[] for _ in range(n + 1)]
md = 1000000007
for i in range(n - 1):
	s = readLine()
	(x, y, t) = (s[0], s[1], s[2])
	if t == 0:
		g[x].append(y)
		g[y].append(x)
ans = deg(n, m)
used = [False for _ in range(n + 1)]
for i in range(1, n + 1):
	if used[i] == False:
		b = bfs(i)
		ans = ans - deg(b, m)
		if ans < 0:
			ans += md
print(ans)


def dfs(x):
	q = [x]
	s[x] = 1
	ans = 1
	while len(q) != 0:
		i = q.pop()
		for y in range(len(w[i])):
			if s[w[i][y]] == 0:
				q.append(w[i][y])
				s[w[i][y]] = 1
				ans = (ans + 1) % e
	return ans
(n, k) = map(int, input().split())
e = 10 ** 9 + 7
w = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		w[a - 1].append(b - 1)
		w[b - 1].append(a - 1)
p = 0
s = [0] * n
for i in range(n):
	if s[i] == 0:
		p += dfs(i) ** k
print((n ** k - p) % e)


from collections import defaultdict as dd
mod = pow(10, 9) + 7

def bfs(s, adj):
	nonlocal parent
	t = 1
	frontier = [s]
	while frontier:
		nex = []
		for u in frontier:
			for v in adj[u]:
				if v not in parent:
					t += 1
					parent.add(v)
					nex.append(v)
		frontier = nex
	return t
adj = dd(list)
(n, k) = [int(i) for i in input().split(' ')]
for ii in range(n - 1):
	(x, y, h) = [int(i) for i in input().split(' ')]
	if h == 0:
		adj[x].append(y)
		adj[y].append(x)
V = [i + 1 for i in range(n)]
parent = set()
fk = []
for i in V:
	if i not in parent:
		parent.add(i)
		tr = bfs(i, adj)
		fk.append(tr)
ans = pow(n, k, mod)
for i in fk:
	ans = (ans - pow(i, k, mod)) % mod
print(ans % mod)


import collections
MOD = 1000000007
(n, k) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v, x) = map(int, input().split())
	u -= 1
	v -= 1
	if x == 0:
		g[u].append(v)
		g[v].append(u)
res = 0
visit = [False] * n
all = pow(n, k, MOD)
bad = 0
for i in range(n):
	if visit[i]:
		continue
	d = collections.deque()
	d.append(i)
	visit[i] = True
	c = 1
	while d:
		u = d.pop()
		for v in g[u]:
			if visit[v]:
				continue
			visit[v] = True
			d.append(v)
			c += 1
	bad += pow(c, k, MOD)
print((all - bad + MOD) % MOD)


import math
import sys

def bfs(start):
	q = [start]
	count = 1
	used[start] = 1
	while q != []:
		for u in g[q[0]]:
			if used[u] == 0:
				count += 1
				used[u] = 1
				q.append(u)
		q.pop(0)
	return count
(n, k) = map(int, input().split())
mod = 10 ** 9 + 7
black = 0
g = [[] for i in range(n)]
for i in range(n - 1):
	(v, u, x) = map(int, input().split())
	v -= 1
	u -= 1
	if x == 0:
		g[v].append(u)
		g[u].append(v)
used = [0] * n
res = 1
r = []
for i in range(n):
	if g[i] != [] and used[i] == 0:
		qq = bfs(i)
		r.append(qq)
for i in range(k):
	res = res * n % mod
for i in range(len(r)):
	rt = 1
	for j in range(k):
		rt = rt * r[i] % mod
	res = (res + mod - rt) % mod
print((res - (n - sum(r)) + mod) % mod)


(n, k) = map(int, input().split())
p = [i for i in range(n + 1)]
sz = [1] * (n + 1)

def par(u):
	if u == p[u]:
		return u
	p[u] = par(p[u])
	return p[u]

def merge(u, v):
	sz[par(v)] += sz[par(u)]
	p[par(u)] = par(v)
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if not x:
		merge(u, v)
MOD = int(1000000000.0 + 7)
ans = n ** k % MOD
uniques = set()
for i in range(1, n + 1):
	parent = par(i)
	if parent in uniques:
		continue
	uniques.add(parent)
	ans -= sz[parent] ** k % MOD
	if ans < 0:
		ans += MOD
print(ans)


MOD = 1000000007
(n, k) = map(int, input().split())
ch = [set() for _ in range(n + 1)]
for _2 in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		ch[u].add(v)
		ch[v].add(u)
res = 0
root = [True] * (n + 1)
for i in range(1, n + 1):
	if root[i]:
		cur = 1
		stack = [i]
		while stack:
			u = stack.pop()
			for v in ch[u]:
				ch[v].remove(u)
				cur += 1
				root[v] = False
				stack.append(v)
		res = (res + pow(cur, k)) % MOD
res = (MOD + pow(n, k) - res) % MOD
print(res)


(n, k) = map(int, input().split())
A = []
for i in range(n):
	A += [[[], 0]]
for i in range(n - 1):
	(u, v, rb) = map(int, input().split())
	if rb == 0:
		A[u - 1][0] += [v - 1]
		A[v - 1][0] += [u - 1]
tr = []
for i in range(len(A)):
	if A[i][1] == 0:
		A[i][1] = 1
		vertices = 1
		can = A[i][0]
		while can:
			nex = []
			for c in can:
				if A[c][1] == 0:
					vertices += 1
					A[c][1] = 1
					nex += A[c][0]
			can = nex
		tr += [vertices]
total = n ** k
for t in tr:
	total -= t ** k
print(total % 1000000007)


def fact(n):
	if n == 0:
		return 1
	else:
		return n * fact(n - 1) % (10 ** 9 + 7)
(n, k) = [int(i) for i in input().split()]
q = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = [int(i) for i in input().split()]
	if c == 0:
		q[a - 1].append(b - 1)
		q[b - 1].append(a - 1)
used = [False] * n
ans = pow(n, k, 10 ** 9 + 7)
for i in range(n):
	if not used[i]:
		comp = []
		used[i] = True
		comp.append(i)
		c = 0
		while c < len(comp):
			for j in q[comp[c]]:
				if not used[j]:
					used[j] = True
					comp.append(j)
			c += 1
		ans = (ans - pow(len(comp), k, 10 ** 9 + 7)) % (10 ** 9 + 7)
print(ans)


(n, k) = [int(i) for i in input().split()]
adj = [[] for i in range(n + 1)]
ans = 0
par = [i for i in range(n + 1)]

def find(i):
	global par
	if par[i] == i:
		return i
	par[i] = find(par[i])
	return par[i]

def unite(i, j):
	global par
	if find(i) < find(j):
		(i, j) = (j, i)
	par[find(i)] = find(j)
for i in range(n - 1):
	(u, v, c) = [int(i) for i in input().split()]
	adj[u].append((v, c))
	adj[v].append((u, c))
	if c == 0:
		unite(u, v)
sz = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	sz[find(i)] += 1
grps = []
for i in range(1, n + 1):
	if find(i) == i:
		grps.append(i)
mod = 10 ** 9 + 7
ans += pow(n, k, mod)
for i in grps:
	ans -= pow(sz[i], k, mod)
	ans += mod
print(ans % mod)


(n, k) = list(map(int, input().split()))
grafo = {}
for _ in range(n - 1):
	(i, j, tipo) = list(map(int, input().split()))
	if tipo == 0:
		l = grafo.get(i, None)
		if l:
			l.append(j)
		else:
			l = [j]
		grafo[i] = l
		l = grafo.get(j, None)
		if l:
			l.append(i)
		else:
			l = [i]
		grafo[j] = l
v = [0] * (n + 1)
g = [0] * (n + 1)
current_group = 0

def passa(pos):
	fila = []
	fila.append(pos)
	global current_group
	global v
	global g
	v[pos] = 1
	current_group += 1
	while fila:
		current = fila.pop(0)
		g[current] = current_group
		l = grafo.get(current, [])
		for i in l:
			if v[i] == 0:
				v[i] = 1
				fila.append(i)
for i in range(1, n + 1):
	if v[i] == 0:
		passa(i)
from collections import Counter
c = Counter(g[1:])
mod_divisor = 1000000007
subtracao = 0
for i in c:
	subtracao += c[i] ** k
print((n ** k - subtracao) % mod_divisor)


from collections import defaultdict
from collections import Counter
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def listt():
	return [int(i) for i in input().split()]
parent = {}
rank = {}
l = []
parent = {}

def find(x):
	lii = []
	while parent[x] != x:
		lii.append(x)
		x = parent[x]
	for i in lii:
		parent[i] = x
	return x

def union(a, b):
	a = find(a)
	b = find(b)
	if a == b:
		return
	if rank[a] > rank[b]:
		parent[b] = a
		rank[a] += rank[b]
	else:
		parent[a] = b
		rank[b] += rank[a]
(n, k) = map(int, input().split())
for i in range(1, n + 1):
	parent[i] = i
	rank[i] = 1
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	if w == 0:
		union(u, v)
s = set()
for i in range(1, n + 1):
	s.add(find(i))
su = 0
for i in s:
	su += rank[i] ** k
print((n ** k - su) % 1000000007)


import sys
[n, k] = list(map(int, sys.stdin.readline().strip().split()))
A = [[] for i in range(0, n)]
C = [0] * n
e = 0
ans = 1
for i in range(0, k // 10):
	ans = ans * n ** 10 % (10 ** 9 + 7)
for i in range(0, k % 10):
	ans = ans * n % (10 ** 9 + 7)
for i in range(0, n - 1):
	line = sys.stdin.readline().strip().split()
	u = int(line[0]) - 1
	v = int(line[1]) - 1
	if int(line[2]) == 0:
		A[u].append(v)
		A[v].append(u)
		e = e + 2
for i in range(0, n):
	if len(A[i]) == 0:
		ans = ans - 1
		C[i] = -1
while e != 0:
	i = 0
	x = 0
	while C[i] == -1:
		i = i + 1
	L = [i]
	while len(L) != 0:
		i = L.pop()
		if C[i] != -1:
			for j in A[i]:
				L.append(j)
				e = e - 1
			x = x + 1
			C[i] = -1
	y = 1
	for i in range(0, k // 10):
		y = y * x ** 10 % (10 ** 9 + 7)
	for i in range(0, k % 10):
		y = y * x % (10 ** 9 + 7)
	ans = ans - y
ans = (ans % (10 ** 9 + 7) + 10 ** 9 + 7) % (10 ** 9 + 7)
print(ans)


(n, k) = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(u, v, c) = list(map(int, input().split()))
	if c == 0:
		g[u].append(v)
		g[v].append(u)
mod = 10 ** 9 + 7

def cal_pow(a, b):
	nonlocal mod
	i = 0
	val = 1
	while i < b:
		val = val * a % mod
		i += 1
	return (val - a + mod) % mod
summ = cal_pow(n, k)
vis = [False for _ in range(n + 1)]
from collections import deque

def bfs(ind):
	q = deque()
	q.append(ind)
	cnt = 0
	vis[ind] = True
	while q:
		indx = q.popleft()
		cnt += 1
		for v in g[indx]:
			if not vis[v]:
				q.append(v)
				vis[v] = True
	return cnt
for v in range(1, n + 1):
	if not vis[v]:
		cnt = bfs(v)
		summ = (mod + summ - cal_pow(cnt, k)) % mod
print(summ)


(N, K) = [int(s) for s in input().split()]
graph = [[] for i in range(N)]
for _ in range(N - 1):
	(a, b, color) = [int(s) - 1 for s in input().split()]
	if color == -1:
		graph[a].append(b)
		graph[b].append(a)
visited = [False] * N
n_component = []
for i in range(N):
	if not visited[i]:
		stack = [i]
		visited[i] = True
		n = 1
		while stack:
			now = stack.pop()
			for v in graph[now]:
				if not visited[v]:
					stack.append(v)
					visited[v] = True
					n += 1
		n_component.append(n)
seq = N ** K
for n in n_component:
	seq -= n ** K
print(seq % (10 ** 9 + 7))


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(i):
	global c
	c += 1
	V[i] = True
	for _ in C[i]:
		if not V[_]:
			yield dfs(_)
	yield
(n, k) = INL()
V = [False for _ in range(n + 1)]
C = dict()
for _ in range(n - 1):
	(u, v, x) = INL()
	if not x:
		if u not in C:
			C[u] = [v]
		else:
			C[u].append(v)
		if v not in C:
			C[v] = [u]
		else:
			C[v].append(u)
ans = 0
for _ in C:
	global c
	c = 0
	if not V[_]:
		dfs(_)
		ans += pow(c, k, MOD())
ans += V[1:].count(False)
OPS((pow(n, k, MOD()) - ans % MOD()) % MOD())


import itertools
(n, k) = list(map(int, input().split()))

class Vert:

	def __init__(self, i):
		self.redir = False
		self.graph = {i}

	def redirect(self, redir_vert):
		self.redir_vert = redir_vert
		self.redir = True
forest = [Vert(i) for i in range(0, n)]

def nedge(edge):
	return [edge[0] - 1, edge[1] - 1, edge[2]]
while True:
	try:
		edge = nedge(list(map(int, input().split())))
		if edge[2] != 1:
			vert1 = forest[edge[0]]
			while vert1.redir:
				vert1 = vert1.redir_vert
			vert2 = forest[edge[1]]
			while vert2.redir:
				vert2 = vert2.redir_vert
			vert1.graph |= vert2.graph
			vert2.redirect(vert1)
	except EOFError:
		break
total_seqs = n ** k
for vert in forest:
	if not vert.redir:
		total_seqs -= len(vert.graph) ** k
print(total_seqs % (10 ** 9 + 7))


(n, k) = map(int, input().split())
maxi = 10 ** 9 + 7

def union(a, x, y, size):
	xs = find(x, a)
	ys = find(y, a)
	if xs == ys:
		return
	elif size[xs] <= size[ys]:
		a[xs] = ys
		size[ys] += size[xs]
	else:
		a[ys] = xs
		size[xs] += size[ys]

def find(i, a):
	if i == a[i]:
		return i
	else:
		a[i] = find(a[i], a)
		return a[i]
a = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]
for i in range(n - 1):
	(p, q, col) = map(int, input().split())
	if col == 0:
		union(a, p, q, size)
s = set()
for i in range(n + 1):
	s.add(find(a[i], a))
s = s - {0}
s = list(s)
sumi = pow(n, k, maxi)
for i in range(len(s)):
	sumi = (sumi - pow(size[s[i]], k, maxi)) % maxi
print(sumi)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7
import math
(n, k) = map(int, input().split())
d = {}
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	d.setdefault(v, [])
	d.setdefault(u, [])
	if x == 0:
		d[u].append(v)
		d[v].append(u)
visited = [0] * n
cnt = 0
tot = n ** k
length = []
stack = []
while cnt != n:
	stack.append(visited.index(0) + 1)
	ans = 1
	while stack:
		node = stack.pop()
		visited[node - 1] = 1
		cnt += 1
		for child in d[node]:
			if visited[child - 1] == 0:
				stack.append(child)
				ans += 1
	length.append(ans)
for c in length:
	tot -= c ** k
print(tot % mod)


intin = lambda : map(int, input().split())
Ain = lambda : list(map(int, input().split()))
mod = 1000000007
(n, k) = intin()
m = n + 1
v = [[] for i in range(m)]
vis = [False] * m
dev = []
for _ in range(n - 1):
	(a, b, x) = intin()
	if x == 0:
		v[a].append(b)
		v[b].append(a)

def dfs(node):
	q = [node]
	cnt = 0
	while len(q) > 0:
		cur = q.pop()
		cnt += 1
		vis[cur] = True
		for i in range(len(v[cur])):
			son = v[cur][i]
			if not vis[son]:
				q.append(son)
	dev.append(cnt)
ans = pow(n, k, mod)
for i in range(1, m):
	if not vis[i]:
		dfs(i)
sub = 0
for i in range(len(dev)):
	cur = dev[i]
	sub = (sub + pow(cur, k, mod)) % mod
ans = (ans - sub + mod) % mod
print(ans)


from collections import defaultdict, deque

def solve(n, k, graph):
	lst = defaultdict(list)
	for (a, b, col) in graph:
		lst[a - 1].append((b - 1, col))
		lst[b - 1].append((a - 1, col))
	components = {}

	def get_component(i):
		visited = set([i])
		component = set([i])
		q = deque([i])
		while q:
			node = q.popleft()
			visited.add(node)
			for (j, col) in lst[node]:
				if j in visited:
					continue
				if col == 0:
					q.append(j)
					component.add(j)
		return component
	components = []
	visited = set()
	for i in range(n):
		if i in visited:
			continue
		component = get_component(i)
		components.append(len(component))
		for j in component:
			visited.add(j)
	ans = n ** k
	for c in components:
		ans -= c ** k
	return ans % (10 ** 9 + 7)
(n, k) = (int(p) for p in input().split())
graph = []
for i in range(n - 1):
	(a, b, col) = (int(p) for p in input().split())
	graph.append((a, b, col))
print(solve(n, k, graph))


from sys import stdin
(n, k) = map(int, stdin.readline().split())
parent = [i for i in range(n + 1)]
size = [1] * (n + 1)
MOD = 10 ** 9 + 7
ans = pow(n, k, MOD)

def find(u):
	if parent[u] == u:
		return u
	parent[u] = find(parent[u])
	return parent[u]
for i in range(n - 1):
	(u, v, c) = map(int, stdin.readline().split())
	if not c:
		pu = find(u)
		pv = find(v)
		size[pu] += size[pv]
		parent[pv] = pu
print((ans - sum([pow(size[u], k, MOD) for u in range(1, n + 1) if parent[u] == u])) % MOD)


import os
from io import BytesIO, StringIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
MOD = 1000000007

def pow(x, p):
	m = 1
	while p > 0:
		m *= x
		p -= 1
		if m >= MOD:
			m %= MOD
	return m
(n, k) = map(int, input().split())
G = [list() for _ in range(n)]
for _ in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		(u, v) = (u - 1, v - 1)
		G[u].append(v)
		G[v].append(u)
set_count = defaultdict(int)
visited = [False] * n
stack = []
for u in range(n):
	if not visited[u]:
		root = u
		stack.append(u)
		while stack:
			u = stack.pop()
			visited[u] = True
			set_count[root] += 1
			for v in G[u]:
				if not visited[v]:
					stack.append(v)
ss = sum((pow(x, k) for x in set_count.values()))
print((pow(n, k) - ss) % MOD)


from collections import defaultdict as ddict
way = ddict(list)
island = list()
went = set()
mini_island = 0

def dfs(nd):
	global mini_island, went
	mini_island += 1
	went.add(nd)
	for it in way[nd]:
		if it not in went:
			dfs(it)
(n, k) = map(int, input().split())
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		way[u - 1].append(v - 1)
		way[v - 1].append(u - 1)
for i in range(n):
	if i not in went:
		stack = [i]
		went.add(i)
		mini_island = 1
		while stack:
			now = stack.pop()
			for v in way[now]:
				if v not in went:
					stack.append(v)
					went.add(v)
					mini_island += 1
		island.append(mini_island)
md = 10 ** 9 + 7
ans = pow(n, k, md)
for it in island:
	ans -= pow(it, k, md)
	ans %= md
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

def bfs(cur):
	tot = 1
	v = [[cur], []]
	used[cur] = True
	vi = 0
	while len(v[vi]):
		for el in v[vi]:
			for nx in g[el]:
				if not used[nx]:
					v[not vi].append(nx)
					used[nx] = True
					tot += 1
		v[vi] = []
		vi = not vi
	return tot
(n, k) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(n - 1):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	if c == 0:
		g[u].append(v)
		g[v].append(u)
used = [False] * n
bad = 0
for i in range(n):
	if not used[i]:
		cur = bfs(i)
		bad += cur ** k
good = n ** k - bad
print(good % MOD)


(n, k) = map(int, input().split())
parent = [i for i in range(n + 1)]
cnt = [1 for _ in range(n + 1)]
mod = 10 ** 9 + 7
ans = n ** k % mod

def find(target):
	if parent[target] == target:
		return target
	parent[target] = find(parent[target])
	return parent[target]

def union(u, v):
	a = find(u)
	b = find(v)
	if cnt[a] < cnt[b]:
		(a, b) = (b, a)
	parent[b] = a
	cnt[a] += cnt[b]
for _ in range(1, n):
	(u, v, x) = map(int, input().split())
	if x == 1:
		continue
	union(u, v)
for j in range(1, n + 1):
	if parent[j] == j:
		val = cnt[j] ** k % mod
		ans = (ans - val) % mod
print(ans)


import collections
(n, k) = map(int, input().split())
visited = [0] * (n + 1)
g = collections.defaultdict(set)
for i in range(n - 1):
	(u, v, color) = map(int, input().split())
	if not color:
		g[u].add(v)
		g[v].add(u)
MOD = 10 ** 9 + 7
ans = pow(n, k, MOD)
for i in range(1, n + 1):
	if not visited[i]:
		sz = 0
		st = [i]
		while st:
			cur = st.pop()
			visited[cur] = 1
			sz += 1
			for node in g[cur]:
				if not visited[node]:
					st.append(node)
		ans -= pow(sz, k, MOD)
		if ans < 0:
			ans += MOD
print(ans)


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict
import math
import heapq

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()
(n, k) = listIn()
di = defaultdict(list)
for i in range(n - 1):
	(u, v, w) = listIn()
	if w == 0:
		di[u].append(v)
		di[v].append(u)
m = 10 ** 9 + 7
final = pow(n, k, m)
vis = [0] * (n + 1)
for i in range(1, n + 1):
	if vis[i] == 0:
		(li, s) = ([i], 1)
		vis[i] = 1
		while li:
			ele = li.pop(-1)
			for p in di[ele]:
				if vis[p] == 0:
					s += 1
					li.append(p)
					vis[p] = 1
		final -= pow(s, k, m)
print(final % m)


import math
import sys
import collections

def In():
	return map(int, sys.stdin.readline().split())
input = sys.stdin.readline

def edgytrees():

	def fastmodpow(n, power, mod):
		res = 1
		x = n
		while power:
			if power % 2:
				res = res * x % mod
			x = x * x % mod
			power //= 2
		return res
	mod = int(1000000000.0 + 7)
	(n, k) = In()
	l = [[] for _ in range(n)]
	for _ in range(n - 1):
		(f, s, c) = In()
		if not c:
			f -= 1
			s -= 1
			l[f].append(s)
			l[s].append(f)
	ans = fastmodpow(n, k, mod)
	visited = [False] * n
	for i in range(n):
		if not visited[i]:
			visited[i] = True
			todo = [i]
			c = 0
			while todo:
				task = todo.pop()
				c += 1
				for x in l[task]:
					if not visited[x]:
						todo.append(x)
						visited[x] = True
			ans -= fastmodpow(c, k, mod)
			ans = (ans + mod) % mod
	return ans
print(edgytrees())


def get(x, p):
	v = x
	while p[v] != v:
		v = p[v]
	while x != v:
		(x, p[x]) = (p[x], v)
	return v
(n, k) = map(int, input().split())
p = [0] * n
sz = [1] * n
for i in range(n):
	p[i] = i
for i in range(n - 1):
	(x, y, z) = map(int, input().split())
	x -= 1
	y -= 1
	if z == 0:
		x = get(x, p)
		y = get(y, p)
		sz[x] += sz[y]
		p[y] = x
mod = 10 ** 9 + 7
ans = pow(n, k, mod)
for i in range(n):
	if p[i] == i:
		ans = (ans - pow(sz[i], k, mod)) % mod
print(ans)


[n, k] = list(map(lambda x: int(x), input().split(' ')))
modulus = 10 ** 9 + 7
components = [None] * (n + 1)

def power(n, k):
	if k == 0:
		return 1
	if n == 1:
		return 1
	if k % 2 == 1:
		return power(n, k // 2) * power(n, k // 2) * n
	else:
		return power(n, k // 2) * power(n, k // 2)

def union_set_compressed_path(elementA, elementB):
	global components
	setA = components[elementA]
	setB = components[elementB]
	if setB and (not setA):
		return union_set_compressed_path(elementB, elementA)
	if setA and (not setB):
		components[elementB] = setA
		return setA
	if setA and setA == setB:
		return setA
	if setA and setB:
		components[elementB] = setA
		union_set_compressed_path(setA, setB)
		return setA
	components[elementA] = elementA
	components[elementB] = elementA
	return elementA

def union_get_compressed_path(element):
	theSet = components[element]
	if theSet == element:
		return theSet
	components[element] = union_get_compressed_path(theSet)
	return components[element]
for i in range(n - 1):
	[u, v, x] = list(map(lambda x: int(x), input().split(' ')))
	v = v
	u = u
	if x == 0:
		union_set_compressed_path(u, v)
	else:
		components[u] = components[u] or u
		components[v] = components[v] or v
componentSize = dict()
for x in range(n):
	key = union_get_compressed_path(x + 1)
	value = (componentSize.get(key) or 0) + 1
	componentSize[key] = value
combinations = power(n, k)
for (key, value) in componentSize.items():
	combinations = (combinations - power(value, k)) % modulus
print(combinations)


import math
import bisect

def argsort(ls):
	return sorted(range(len(ls)), key=ls.__getitem__)

def f(p=0):
	if p == 0:
		return int(input())
	if p == 1:
		return map(int, input().split())
	elif p == 2:
		return list(map(int, input().split()))
	else:
		return sorted(list(map(int, input().split())))
(n, k) = f(1)
dl = [0] * (n + 1)
dl[0] = -1
g = [list() for i in range(n + 1)]
for i in range(n - 1):
	(u, v, x) = f(1)
	if x == 0:
		g[u].append(v)
		g[v].append(u)
cl = []
queue = [1]
count = n
for i in range(1, n + 1):
	if dl[i] != 1:
		queue = [i]
		for x in queue:
			count -= 1
			dl[x] = 1
			for v in g[x]:
				if dl[v] != 1:
					queue.append(v)
		cl.append(list(queue))
res = n ** k % (10 ** 9 + 7)
for x in cl:
	t = len(x)
	t = t ** k % (10 ** 9 + 7)
	res -= t
print(res % (10 ** 9 + 7))


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
(n, k) = mapin()
d = defaultdict(list)
for _ in range(n - 1):
	(u, v, z) = mapin()
	if not z:
		d[u - 1].append(v - 1)
		d[v - 1].append(u - 1)
mark = [0] * n
tree_num = 1
for i in range(n):
	if not mark[i]:
		mark[i] = tree_num
		q = deque([i])
		while q:
			first = q.pop()
			for j in d[first]:
				if not mark[j]:
					mark[j] = tree_num
					q.append(j)
		tree_num += 1
count = defaultdict(int)
for i in mark:
	count[i] += 1
ex = 0
mod = 10 ** 9 + 7
for i in count.values():
	ex += pow(i, k, mod)
print((pow(n, k, mod) + mod - ex) % mod)


import sys

class E:

	def __init__(self, fr, to, c):
		self.fr = fr - 1
		self.to = to - 1
		self.c = c

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = sys.stdin.readline().split()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_int(self):
		return int(self.next())

	def solve(self):
		n = self.next_int()
		k = self.next_int()
		fa = [-1 for _ in range(0, n)]
		sz = [1 for _ in range(0, n)]
		for _ in range(1, n):
			fr = self.find(self.next_int() - 1, fa)
			to = self.find(self.next_int() - 1, fa)
			c = self.next_int()
			if c == 0 and fr != to:
				sz[fr] += sz[to]
				fa[to] = fr
		mod = 1000000007
		ans = self.pp(n, k, mod)
		for i in range(0, n):
			if fa[i] == -1:
				ans = (ans + mod - self.pp(sz[i], k, mod)) % mod
		print(ans)

	def find(self, k, fa):
		if fa[k] == -1:
			return k
		fa[k] = self.find(fa[k], fa)
		return fa[k]

	def pp(self, n, k, mod):
		if k == 0:
			return 1
		tmp = self.pp(n, k // 2, mod)
		tmp = tmp * tmp % mod
		if k % 2 == 1:
			tmp = tmp * n % mod
		return tmp
Main().solve()


def parent(p, x):
	if p[x] == x:
		return x
	p[x] = parent(p, p[x])
	return p[x]
(n, m) = map(int, input().split())
p = []
for i in range(n):
	p.append(i)
s = []
for i in range(n):
	s.append(1)
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		a -= 1
		b -= 1
		pa = parent(p, a)
		pb = parent(p, b)
		if pa == pb:
			continue
		elif s[pa] < s[pb]:
			p[pa] = pb
			s[pb] += s[pa]
		else:
			p[pb] = pa
			s[pa] += s[pb]
temp = 0
for i in range(n):
	if parent(p, i) == i:
		temp += s[i] ** m
		temp = temp % 1000000007
print((n ** m - temp + 1000000007) % 1000000007)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}
(n, k) = inpl()
uf = UnionFind(n)
for _ in range(n - 1):
	(a, b, c) = inpl()
	if c == 0:
		uf.union(a - 1, b - 1)
d = defaultdict(list)
for i in range(n):
	now = uf.find(i)
	if now < 0:
		d[i].append(i)
	else:
		d[now].append(i)
su = 0
for key in list(d):
	m = len(d[key])
	su += pow(m, k, mod)
print((pow(n, k, mod) - su) % mod)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import *

def power(a, b, mod):
	res = 1
	while b:
		if b % 2:
			res = res * a % mod
		b //= 2
		a = a * a % mod
	return res % mod
MOD = 1000000007
(n, k) = map(int, input().split())
ans = power(n, k, MOD)
adj = defaultdict(list)
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if not x:
		adj[u].append(v)
		adj[v].append(u)
v = [0] * (1 + n)
for i in range(1, 1 + n):
	if not v[i]:
		cmp = 0
		q = [i]
		while q:
			e = q.pop()
			if not v[e]:
				cmp += 1
			v[e] = 1
			for j in adj[e]:
				if not v[j]:
					q.append(j)
		ans = (ans % MOD - power(cmp, k, MOD)) % MOD
print(ans)


from math import floor
(n, k) = map(int, input().split())
childs = [[] for i in range(n + 1)]
for i in range(n - 1):
	(i, j, color) = map(int, input().split())
	childs[i].append((j, color))
	childs[j].append((i, color))
stack = [(1, 0, 1)]
record = [0] * (n + 1)
vis = [False] * (n + 1)
ans = 0
MOD = floor(1000000000.0 + 7)
while len(stack):
	(node, parent, fcolor) = stack[-1]
	if not vis[node]:
		vis[node] = True
		for (child, color) in childs[node]:
			if child != parent:
				stack.append((child, node, color))
	else:
		stack.pop()
		record[node] = 1
		for (child, color) in childs[node]:
			if child != parent and color == 0:
				record[node] += record[child]
		if fcolor:
			ans = (ans + pow(record[node], k, MOD)) % MOD
print((pow(n, k, MOD) - ans + MOD) % MOD)


from __future__ import division, print_function
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import BytesIO, IOBase

class FastI:

	def __init__(self, fd=0, buffersize=2 ** 14):
		(self.stream, self.bufflines) = (BytesIO(), 0)

		def read2buffer(stream):
			(curpos, s) = (stream.tell(), os.read(fd, buffersize + os.fstat(fd).st_size))
			return [s, stream.seek(0, 2), stream.write(s), stream.seek(curpos)][0]
		self.read2buffer = lambda : read2buffer(self.stream)
		self.input = lambda : self.readline().rstrip(b'\r\n')

	def read(self):
		while self.read2buffer():
			pass
		return self.stream.read()

	def readline(self):
		while self.bufflines == 0:
			s = self.read2buffer()
			self.bufflines += s.count(b'\n') + (not s)
		self.bufflines -= 1
		return self.stream.readline()

class FastO(IOBase):

	def __init__(self, fd=1):
		stream = BytesIO()
		self.flush = lambda : os.write(fd, stream.getvalue()) + stream.truncate(0)
		self.write = stream.write if py2 else lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
input = sys.stdin.input

def readLine():
	return [int(i) for i in input().split()]

def deg(x, y):
	if y == 1:
		return x
	res = deg(x, y // 2)
	res *= res
	res %= md
	if y % 2 == 1:
		res *= x
		res %= md
	return res

def dfs(v):
	Q = [v]
	used[v] = True
	c = 0
	while Q:
		v = Q.pop()
		c += 1
		for to in g[v]:
			if not used[to]:
				used[to] = True
				Q.append(to)
	return c
(n, m) = readLine()
g = [[] for _ in range(n + 1)]
md = 1000000007
for i in range(n - 1):
	(x, y, t) = readLine()
	if t == 0:
		g[x].append(y)
		g[y].append(x)
ans = deg(n, m)
used = [False] * (n + 1)
for i in range(1, n + 1):
	if used[i] == False:
		b = dfs(i)
		ans = ans - deg(b, m)
		if ans < 0:
			ans += md
print(ans)


def n_perm_k(n, k):
	return n ** k

def ways(xs, k):
	total = n_perm_k(sum(xs), k)
	for x in xs:
		total -= n_perm_k(x, k)
	return total

def dfs(i, graph, visited):
	stack = [i]
	count = 0
	while stack:
		current = stack.pop()
		count += 1
		visited.add(current)
		for (neighbor, black) in graph[current].items():
			if not black and neighbor not in visited:
				stack.append(neighbor)
	return count

def get_forest_sizes(n, graph):
	visited = set()
	components = []
	for i in range(1, n + 1):
		if i not in visited:
			ans = dfs(i, graph, visited)
			components.append(ans)
	return components

def solve(n, k, graph, black_count):
	if black_count == 0:
		return 0
	else:
		return ways(get_forest_sizes(n, graph), k)
(n, k) = map(int, input().split())
graph = {x: {} for x in range(1, n + 1)}
black_count = 0
for _ in range(1, n):
	(a, b, black) = map(int, input().split())
	black_count += black
	graph[a][b] = black == 1
	graph[b][a] = black == 1
print(solve(n, k, graph, black_count) % (10 ** 9 + 7))


from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
(n, k) = mapi()
size = [1] * (n + 1)
par = [i for i in range(n + 1)]

def find(x):
	if par[x] == x:
		return x
	par[x] = find(par[x])
	return par[x]

def union(a, b):
	if a == b:
		return
	if find(a) == find(b):
		return
	a = find(a)
	b = find(b)
	if size[a] > size[b]:
		(a, b) = (b, a)
	size[b] += size[a]
	par[a] = b
for i in range(n - 1):
	(a, b, x) = mapi()
	if x == 0:
		union(a, b)
mod = int(1000000000.0 + 7)
res = pow(n, k, mod)
for i in range(1, n + 1):
	if find(i) == i:
		res = (res - pow(size[i], k, mod) + mod) % mod
print(res)


(n, k) = map(int, input().split())
r = [0]
for i in range(1, n + 1):
	r.append(i)
nd = [1] * (n + 1)
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if not x:
		while r[r[u]] != r[u]:
			r[u] = r[r[u]]
		while r[r[v]] != r[v]:
			r[v] = r[r[v]]
		if nd[r[u]] >= nd[r[v]]:
			nd[r[u]] += nd[r[v]]
			r[r[v]] = r[u]
		else:
			nd[r[v]] += nd[r[u]]
			r[r[u]] = r[v]
for i in range(1, 1 + n):
	while r[r[i]] != r[i]:
		r[i] = r[r[i]]
c = n ** k
for i in range(1, 1 + n):
	if r[i] == i:
		c -= nd[i] ** k
y = 7 + 10 ** 9
print(c % y)


from collections import deque
import sys, math

def get_int():
	return list(map(int, sys.stdin.readline().strip().split()))
mod = 10 ** 9 + 7

def dfs(adj_list, n):
	v_list = [False] * (n + 1)
	v_list[0] = None
	comp_cnt = []
	for u in range(1, n + 1):
		if v_list[u] == False:
			q = deque([u])
			v_list[u] = True
			c = 1
			while len(q) > 0:
				v = deque.popleft(q)
				for w in adj_list[v]:
					if v_list[w] == False:
						c += 1
						v_list[w] = True
						deque.append(q, w)
			comp_cnt.append(c)
	return comp_cnt

def power(x, y, p=mod):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
(n, k) = get_int()
adj_list = [[] for _ in range(n + 1)]
adj_list[0] = None
for _ in range(n - 1):
	(a, b, c) = get_int()
	if c == 0:
		adj_list[a].append(b)
		adj_list[b].append(a)
comp_stngth = dfs(adj_list, n)
t_pos = power(n, k)
n_pos = 0
for c in comp_stngth:
	n_pos = (n_pos + power(c, k)) % mod
print((t_pos - n_pos) % mod)


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

def get(cur, d, seen):
	queue = deque([cur])
	compo = []
	while len(queue):
		cur = queue.popleft()
		if cur not in seen:
			seen.add(cur)
			compo.append(cur)
			for neigh in d.get(cur, []):
				queue.append(neigh)
	return len(compo)
(n, k) = iia()
d = {}
for i in range(n - 1):
	(u, v, c) = iia()
	if c == 0:
		d.setdefault(u, []).append(v)
		d.setdefault(v, []).append(u)
seen = set()
res = 0
for i in range(1, n + 1):
	if i not in seen:
		res += pow(get(i, d, seen), k, mod)
		res %= mod
res = pow(n, k, mod) - res
print(res % mod)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
EDGE = [list(map(int, input().split())) for i in range(n - 1)]
mod = 10 ** 9 + 7
Group = [i for i in range(n + 1)]

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
for (x, y, c) in EDGE:
	if c == 0:
		Union(x, y)
G = [find(i) for i in range(1, n + 1)]
from collections import Counter
counter = Counter(G)
ANS = 0
for j in counter.values():
	ANS = (ANS + pow(j, k, mod)) % mod
print((pow(n, k, mod) - ANS) % mod)


(n, k) = map(int, input().strip().split())
l = [[] for i in range(n + 1)]
used = [False for i in range(n + 1)]
for i in range(n - 1):
	(u, v, x) = map(int, input().strip().split())
	if x == 0:
		l[v].append(u)
		l[u].append(v)
components = []

def func(l, v, components, used):
	vert = [v]
	used[v] = True
	temp = l[v]
	while temp != []:
		newverts = []
		for i in temp:
			used[i] = True
			for j in l[i]:
				if used[j] == False:
					newverts.append(j)
					used[j] = True
		for i in temp:
			vert.append(i)
		temp = newverts
	components.append(len(vert))
for i in range(1, n + 1):
	if used[i] == False:
		func(l, i, components, used)
ans = pow(n, k, 1000000007)
for i in components:
	ans -= pow(i, k, 1000000007)
	ans = ans % 1000000007
print(ans)


from collections import defaultdict
from collections import Counter
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from threading import stack_size, Thread
sys.setrecursionlimit(10 ** 6)
stack_size(10 ** 8)

def listt():
	return [int(i) for i in input().split()]
count = 0
dic = {}
visited = {}

def dfs(src):
	global count, visited, dic
	count += 1
	visited[src] = 1
	for i in dic[src]:
		if visited[i] == 0:
			dfs(i)
	return count

def main():
	global count, visited, dic
	(n, k) = map(int, input().split())
	dic = {}
	visited = {}
	for i in range(1, n + 1):
		visited[i] = 0
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		if w == 0:
			if u in dic:
				dic[u].append(v)
			else:
				dic[u] = [v]
			if v in dic:
				dic[v].append(u)
			else:
				dic[v] = [u]
		else:
			if u in dic:
				dic[u].append(u)
			else:
				dic[u] = [u]
			if v in dic:
				dic[v].append(v)
			else:
				dic[v] = [v]
	l = []
	for i in dic:
		if visited[i] == 0:
			count = 0
			l.append(dfs(i))
	su = 0
	for i in l:
		su += i ** k
	print((n ** k - su) % 1000000007)
Thread(target=main).start()


import sys, threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)

def main():
	global al, va
	mod = 1000000007
	(n, m) = map(int, input().split())
	al = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b, c) = map(int, input().split())
		if c == 0:
			al[a].append(b)
			al[b].append(a)
	va = [0] * (n + 1)
	ans = pow(n, m, mod)
	for e in range(1, n + 1):
		if va[e] == 0:
			global co
			co = 0
			dfs(e)
			ans = ans - pow(co, m, mod)
			ans = ans % mod
	print(ans)

def dfs(n):
	global al, va, co
	va[n] = 1
	co = co + 1
	for e in al[n]:
		if va[e] == 0:
			dfs(e)
t = threading.Thread(target=main)
t.start()
t.join()


def union(a, b, root):
	ra = a
	rb = b
	while ra != root[ra]:
		ra = root[root[ra]]
	while rb != root[rb]:
		rb = root[root[rb]]
	if ra != rb:
		root[rb] = ra
		size[ra] += size[rb]
		size[rb] = 0
(n, k) = map(int, input().split())
mod = int(1000000000.0 + 7)
root = [0] * n
size = [1] * n
for i in range(n):
	root[i] = i
for i in range(1, n):
	(a, b, c) = map(int, input().split())
	if c == 0:
		union(a - 1, b - 1, root)
allcom = pow(n, k)
failedcom = 0
for ele in size:
	if ele != 0:
		failedcom += pow(ele, k)
print((allcom - failedcom) % mod)


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

class UnionFind:

	def __init__(self, size):
		self.parent = [i for i in range(size)]
		self.rank = [0 for _ in range(size)]
		self.conN = [1 for _ in range(size)]

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			return self.find(self.parent[x])

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.parent[x] = y
			self.conN[y] += self.conN[x]
		else:
			self.parent[y] = x
			self.conN[x] += self.conN[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def component(self):
		comp = set()
		for i in self.parent:
			p = self.find(i)
			comp.add(p)
		return comp

	def componentNumm(self):
		return len(self.component())

	def connectedNum(self, x):
		p = self.find(x)
		return self.conN[p]

	def __str__(self):
		ret = 'parents\n'
		ret += ' '.join(map(str, self.parent))
		ret += '\n'
		ret += ' '.join(map(str, self.rank))
		return ret
MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
Un = UnionFind(N)
for _ in range(N - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		a -= 1
		b -= 1
		Un.union(a, b)
noGood = 0
parent = set()
for i in range(N):
	p = Un.find(i)
	if p in parent:
		continue
	else:
		parent.add(p)
		noGood += pow(Un.connectedNum(p), K, MOD)
ans = pow(N, K, MOD) - noGood
if ans < 0:
	ans += MOD
ans %= MOD
print(ans)


a = lambda : map(int, input().split())
s = lambda : list(a())
(d, f) = a()
z = {i: {i} for i in range(d)}
x = {i: i for i in range(d)}
for i in range(d - 1):
	(c, v, q) = a()
	(c, v) = (c - 1, v - 1)
	if q == 0:
		(w, e) = (z[x[c]], z[x[v]])
		if len(w) > len(e):
			w |= e
			del z[x[v]]
			for o in e:
				x[o] = x[c]
		else:
			e |= w
			del z[x[c]]
			for o in w:
				x[o] = x[v]
r = 0
for i in z:
	r += len(z[i]) ** f
print((d ** f - r) % (7 + 10 ** 9))


import collections
p = 10 ** 9 + 7
(n, k) = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b, x) = list(map(int, input().split()))
	if x != 0:
		continue
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
v = [False] * n
bad = 0
for i in range(n):
	if v[i]:
		continue
	d = collections.deque()
	d.append(i)
	v[i] = True
	c = 0
	while d:
		i = d.pop()
		for j in g[i]:
			if v[j]:
				continue
			v[j] = True
			d.append(j)
		c += 1
	bad += pow(c, k, p)
print((pow(n, k, p) + p - bad) % p)


import sys
import os.path
Base = 1000000007

class Dsu:
	par = []
	cnt = []

	def __init__(self, size):
		self.par = [x for x in range(size + 2)]
		self.cnt = [1] * (size + 2)

	def findp(self, u):
		if self.par[u] == u:
			return u
		else:
			self.par[u] = self.findp(self.par[u])
			return self.par[u]

	def join(self, u, v):
		(u, v) = (self.findp(u), self.findp(v))
		if u == v:
			return
		if self.cnt[u] < self.cnt[v]:
			(u, v) = (v, u)
		self.cnt[u] += self.cnt[v]
		self.par[v] = u

	def getSize(self, u):
		return self.cnt[self.findp(u)]

def mulmod(u, v):
	return u % Base * (v % Base) % Base

def submod(u, v):
	return (u % Base - v % Base + Base) % Base

def fastExp(x, h):
	ret = 1
	while h > 0:
		if h & 1 == 1:
			ret = mulmod(ret, x)
		x = mulmod(x, x)
		h = h // 2
	return ret

def solve():
	(n, k) = map(int, input().split())
	dsu = Dsu(n)
	for i in range(1, n):
		(u, v, x) = map(int, input().split())
		if x == 0:
			dsu.join(u, v)
	ans = fastExp(n, k)
	for u in range(1, n + 1):
		if dsu.findp(u) == u:
			ans = submod(ans, fastExp(dsu.getSize(u), k))
	print(ans)

def main():
	if os.path.exists('test.inp'):
		sys.stdin = open('test.inp', 'r')
	solve()
main()


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
(n, k) = ri()
l = dd(list)
vis = [0 for i in range(n + 1)]

def bfs(s):
	d = [s]
	sz = 1
	vis[s] = 1
	while d:
		k = d.pop(0)
		for i in l[k]:
			if vis[i] == 0:
				vis[i] = 1
				d.append(i)
				sz += 1
	return sz
for i in range(n - 1):
	(u, v, r) = ri()
	if r == 0:
		l[u].append(v)
		l[v].append(u)
ans = pow(n, k, mod)
for i in range(1, n + 1):
	if vis[i] == 0:
		m = bfs(i)
		ans = (ans - pow(m, k, mod)) % mod
print(ans)


import sys
from collections import defaultdict, deque
length = sys.stdin.readline().strip().split(' ')
(n, k) = map(int, length)
graph = defaultdict(list)
for _ in range(int(n - 1)):
	line = sys.stdin.readline().strip().split(' ')
	if int(line[2]) == 0:
		graph[int(line[0])].append(int(line[1]))
		graph[int(line[1])].append(int(line[0]))
	else:
		if int(line[0]) not in graph:
			graph[int(line[0])] = []
		if int(line[1]) not in graph:
			graph[int(line[1])] = []
visited = set()

def bfs(graph, visited):
	queue = deque()
	graph_parts_sizes = []
	for vertex in graph:
		if vertex in visited:
			continue
		prev_size = len(visited)
		queue.append(vertex)
		while len(queue) != 0:
			vertex = queue.popleft()
			visited.add(vertex)
			for neighbour in graph[vertex]:
				if neighbour not in visited:
					queue.append(neighbour)
		graph_parts_sizes.append(len(visited) - prev_size)
	return graph_parts_sizes
parts_size = bfs(graph, visited)
MODULO = int(1000000000.0 + 7)
answer = n ** k % MODULO
for size in parts_size:
	answer -= size ** k % MODULO
	answer %= MODULO
print(answer % MODULO)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
(vertices, limit) = RMI()
graph = [[] for _ in range(vertices)]
for i in range(vertices - 1):
	(u, v, x) = RMI()
	graph[u - 1].append((v - 1, x))
	graph[v - 1].append((u - 1, x))
done = [0 for _ in range(vertices)]
comps = []
for i in range(vertices):
	if done[i]:
		continue
	done[i] = 1
	comps.append([i])
	qu = [i]
	while qu:
		curr_u = qu[0]
		qu = qu[1:]
		for (u, x) in graph[curr_u]:
			if x == 0 and done[u] == 0:
				qu.append(u)
				done[u] = 1
				comps[-1].append(u)
answer = vertices ** limit
for comp in comps:
	answer -= len(comp) ** limit
print(answer % (10 ** 9 + 7))


(n, k) = map(int, input().split())
li = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v, c) = map(int, input().split())
	li[u].append((v, c))
	li[v].append((u, c))
stack = [(1, 0)]
(i, j) = (0, 0)
start = [0]
visited = [False] * (n + 1)
while len(stack) != 0:
	popped = stack.pop()
	item = popped[0]
	if not visited[item]:
		start[popped[1]] += 1
	visited[item] = True
	for i in range(len(li[item])):
		child = li[item][i]
		if not visited[child[0]]:
			if child[1] == 0:
				stack.append((child[0], popped[1]))
			else:
				start.append(0)
				pos = len(start) - 1
				stack.append((child[0], pos))
ans = n ** k
for i in start:
	ans = ans - i ** k
print(ans % (10 ** 9 + 7))


def union(x, y, sets: list, parents: list, inds: set):
	x = parents[x]
	y = parents[y]
	if x == y:
		return
	if len(sets[x]) > len(sets[y]):
		(x, y) = (y, x)
	inds.discard(x)
	for nd in sets[x]:
		parents[nd] = y
		sets[y].append(nd)
(n, k) = map(int, input().split())
parents = list(range(n))
sets = [[i] for i in range(n)]
inds = set(range(n))
for _ in range(n - 1):
	(x, y, c) = map(int, input().split())
	x -= 1
	y -= 1
	if c == 0:
		union(x, y, sets, parents, inds)
cnt = n ** k
for i in inds:
	cnt -= len(sets[i]) ** k
print(cnt % (10 ** 9 + 7))


import sys
input = sys.stdin.readline
from collections import deque
mod = int(1000000000.0) + 7
(n, k) = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c:
		continue
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
v = [False] * n
ans = 0
for i in range(n):
	if not v[i]:
		q = deque([i])
		v[i] = True
		s = 0
		while q:
			node = q.popleft()
			s += 1
			for j in graph[node]:
				if not v[j]:
					v[j] = True
					q.append(j)
		ans = (ans % mod + pow(s, k, mod)) % mod
print((pow(n, k, mod) % mod - ans % mod) % mod)


import collections
p = 10 ** 9 + 7
(n, k) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(1, n):
	(a, b, x) = map(int, input().split())
	if x == 0:
		graph[a].append(b)
		graph[b].append(a)
visited = [False] * (n + 1)
bad = 0
queue = collections.deque()
for i in range(1, n + 1):
	if not visited[i]:
		queue.append(i)
		visited[i] = True
		size_connected_component = 0
		while queue:
			front = queue.pop()
			for adj_front in graph[front]:
				if not visited[adj_front]:
					visited[adj_front] = True
					queue.append(adj_front)
			size_connected_component += 1
		bad += pow(size_connected_component, k, p)
print((pow(n, k, p) + p - bad) % p)


mod = 1000000007
(n, k) = map(int, input().split())
parent = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]

def find(node):
	if parent[node] == node:
		return node
	parent[node] = find(parent[node])
	return parent[node]
for i in range(n - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		pa = find(parent[a])
		pb = find(parent[b])
		size[pa] += size[pb]
		parent[pb] = pa
ans = n ** k % mod
for i in range(1, n + 1):
	if parent[i] == i:
		ans -= size[i] ** k % mod
print(ans % mod)


(N, k) = map(int, input().split())
MOD = 10 ** 9 + 7
gr = [-1] * N
G = [[] for i in range(N)]
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	if c == 0:
		G[a - 1].append(b - 1)
		G[b - 1].append(a - 1)
g = 0
for i in range(N):
	if gr[i] == -1:
		que = [i]
		while que:
			j = que.pop()
			gr[j] = g
			for w in G[j]:
				if gr[w] == -1:
					que.append(w)
		g += 1
num = 0
ans = N ** k % MOD
d = [0] * N
for i in range(N):
	if gr[i] != -1:
		d[gr[i]] += 1
for i in range(N):
	num += d[i] ** k
	num %= MOD
print((ans - num + MOD) % MOD)


import sys
import math

def getAndParseInt(num=1):
	string = sys.stdin.readline().strip()
	if num == 1:
		return int(string)
	else:
		return [int(part) for part in string.split()]

def getAndParseString(num=1, delim=' '):
	string = sys.stdin.readline().strip()
	if num == 1:
		return string
	else:
		return [part for part in string.split(delim)]
(n, k) = getAndParseInt(2)
adj_list = [[] for i in range(n + 1)]
binary_k = []
temp = k
while temp > 0:
	binary_k.append(temp % 2)
	temp = temp // 2
for i in range(n - 1):
	(u, v, c) = getAndParseInt(2)
	if c != 1:
		adj_list[u].append(v)
		adj_list[v].append(u)
marked = [0] * (n + 1)
modulo = 1000000007

def powerMod(base):
	maxp = len(binary_k) - 1
	index = 0
	val = base % modulo
	ret_val = 1
	while index <= maxp:
		if binary_k[index]:
			ret_val = ret_val * val % modulo
		val = val * val % modulo
		index += 1
	return ret_val

def dfs(vertex):
	stack = [vertex]
	size = 0
	while stack:
		cur = stack.pop()
		marked[cur] = 1
		size += 1
		for child in adj_list[cur]:
			if not marked[child]:
				stack.append(child)
	return size
total = powerMod(n)
for vertex in range(1, n + 1):
	if not marked[vertex]:
		count = dfs(vertex)
		total = (total - powerMod(count)) % modulo
print(total)


import sys
from collections import Counter as CO
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
input = sys.stdin.readline

def find(parent, x):
	if x != parent[x]:
		parent[x] = find(parent, parent[x])
	return parent[x]

def union(parent, x, y):
	parent[x] = find(parent, x)
	parent[y] = find(parent, y)
	if parent[x] == parent[y]:
		return 1
	elif parent[x] < parent[y]:
		parent[parent[x]] = parent[y]
	else:
		parent[parent[y]] = parent[x]
(n, k) = map(int, input().split())
parent = [0] * n
for i in range(n):
	parent[i] = i
for i in range(n - 1):
	(a, b, ex) = map(int, input().split())
	a -= 1
	b -= 1
	if ex == 0:
		union(parent, a, b)
for i in range(n):
	parent[i] = find(parent, i)
ans = 0
freq = dict(CO(parent))
for i in freq:
	ans = (ans + pow(freq[i], k, mod)) % mod
ans = pow(n, k, mod) - ans
if ans < 0:
	ans += mod
print(ans % mod)


MOD = int(1000000000.0 + 7)

def join(a, b):
	par[root(u)] = v

def root(u):
	if u == par[u]:
		return u
	par[u] = root(par[u])
	return par[u]

def bigmod(a, b):
	ret = 1
	while b != 0:
		if b % 2 == 1:
			ret *= a
			ret %= MOD
		b //= 2
		a *= a
		a %= MOD
	return ret
(n, m) = map(int, input().split())
par = [i for i in range(0, n + 1)]
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		join(u, v)
cnt = [0] * (n + 1)
for i in range(1, n + 1):
	cnt[root(i)] += 1
ans = 0
for i in range(1, n + 1):
	ans += bigmod(cnt[i], m)
	ans %= MOD
ans = bigmod(n, m) - ans
ans %= MOD
ans = (ans + MOD) % MOD
print(ans)


(n, k) = map(int, input().split())
(g, s, v, m, cs) = ([[] for _ in range(n + 1)], 0, [0] * (n + 1), 10 ** 9 + 7, [])
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	if not c:
		g[a].append(b)
		g[b].append(a)
for i in range(1, n + 1):
	if not v[i]:
		cs.append(i)
		v[i] = 1
		res = 0
		while cs:
			p = cs.pop()
			for j in g[p]:
				if not v[j]:
					cs.append(j)
					v[j] = 1
			res += 1
		s += pow(res, k, m)
print((pow(n, k, m) - s) % m)


from sys import setrecursionlimit
import threading
setrecursionlimit(10 ** 9)
threading.stack_size(67108864)

def dfs(i):
	global used, g, kol
	kol += 1
	for c in g[i]:
		if not used[c]:
			used[c] = True
			dfs(c)
kol = 0
used = []
g = []

def main():
	global kol, used, g
	(n, k) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y, z) = map(int, input().split())
		if z == 0:
			g[x].append(y)
			g[y].append(x)
	ans = n ** k
	used = [False] * (n + 1)
	for i in range(1, n + 1):
		kol = 0
		if not used[i]:
			kol = 0
			used[i] = True
			dfs(i)
			ans -= kol ** k
	print(ans % (10 ** 9 + 7))
	pass
thread = threading.Thread(target=main)
thread.start()


(n, k) = map(int, input().split())
md = 10 ** 9 + 7
res = n ** k
neighbours = {}
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		if u in neighbours:
			neighbours[u].add(v)
		else:
			neighbours[u] = set([v])
		if v in neighbours:
			neighbours[v].add(u)
		else:
			neighbours[v] = set([u])
comp = []
visited = [0] * (n + 1)
for i in range(1, n + 1):
	if not visited[i]:
		comp.append([i])
		visited[i] = 1
		q = [i]
		while len(q) > 0:
			u = q.pop(0)
			if u not in neighbours:
				continue
			for v in neighbours[u]:
				if not visited[v]:
					q.append(v)
					comp[-1].append(v)
					visited[v] = 1
for c in comp:
	m = len(c)
	res -= m ** k
print(res % md)


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
MOD = 10 ** 9 + 7
(n, k) = mi()
(p, s) = (list(range(n + 1)), [1] * (n + 1))

def find(x):
	if p[x] != x:
		p[x] = find(p[x])
	return p[x]

def union(x, y):
	(x, y) = (find(x), find(y))
	if x == y:
		return
	if s[x] < s[y]:
		(x, y) = (y, x)
	p[y] = x
	s[x] += s[y]
for _ in range(n - 1):
	(u, v, c) = mi()
	if c == 0:
		union(u, v)
grps = []
for u in range(1, n + 1):
	if p[u] == u:
		grps.append(s[u])
ans = (pow(n, k, MOD) - sum((pow(x, k, MOD) for x in grps))) % MOD
print(ans)


from collections import defaultdict, deque
MOD = 10 ** 9 + 7

def bfs(v):
	q.append(v)
	visited[v] = True
	while q:
		s = q.popleft()
		b.append(v)
		for i in g[s]:
			if not visited[i[0]] and i[1] == 0:
				q.append(i[0])
				visited[i[0]] = True
(n, k) = list(map(int, input().split()))
g = defaultdict(list)
for _ in range(n - 1):
	(x, y, c) = list(map(int, input().split()))
	g[x].append((y, c))
	g[y].append((x, c))
visited = [False] * (n + 1)
count = 0
ans = pow(n, k, MOD)
q = deque()
for i in range(1, n + 1):
	b = []
	if visited[i] == False:
		bfs(i)
	f = len(b)
	count = (count + pow(f, k, MOD)) % MOD
ans = (ans - count) % MOD
print(ans)


import functools
(nodes_nr, seq_len) = (int(x) for x in input().split())
node_idx___red_children = [[] for _ in range(nodes_nr)]
mod = 10 ** 9 + 7
for _ in range(nodes_nr - 1):
	(n1, n2, color) = (int(x) for x in input().split())
	if color == 0:
		node_idx___red_children[n1 - 1].append(n2 - 1)
		node_idx___red_children[n2 - 1].append(n1 - 1)
node_idx___component = [-1 for _ in range(nodes_nr)]
component___size = []
curr_component = 0
for node in range(nodes_nr):
	if node_idx___component[node] != -1:
		continue
	curr_component_size = 1
	stack = [node]
	node_idx___component[node] = curr_component
	while len(stack) > 0:
		node_idx = stack.pop()
		for child_idx in node_idx___red_children[node_idx]:
			if node_idx___component[child_idx] == -1:
				node_idx___component[child_idx] = curr_component
				curr_component_size += 1
				stack.append(child_idx)
			elif node_idx___component[child_idx] != curr_component:
				raise Exception('Two connectivity components are connected somehow. Go investigate it')
	component___size.append(curr_component_size)
	curr_component += 1
ans = pow(nodes_nr, seq_len, mod)
for size in component___size:
	ans -= pow(size, seq_len, mod)
	ans %= mod
print((ans % mod + mod) % mod)


import sys
sys.setrecursionlimit(30000)

def gcd(n, p):
	if n in v:
		answer = 1
		time = set([n])
		invite.add(n)
		counter = 1
		timer = set([n])
		while counter > 0:
			time = timer
			timer = set()
			counter = 0
			for item in time:
				for i in v[item]:
					if i not in invite:
						timer.add(i)
						invite.add(i)
						counter += 1
			answer += counter
		return answer
	return 1
v = {}
counter = 0
invite = set()
(n, k) = [int(x) for x in input().split()]
for i in range(n - 1):
	(a, b, c) = [int(x) for x in input().split()]
	if c == 0:
		for (i, j) in ((a, b), (b, a)):
			if i not in v:
				v[i] = set([j])
			else:
				v[i].add(j)
for i in range(1, n + 1):
	if i not in invite:
		counter += pow(gcd(i, 0), k)
print((pow(n, k) - counter) % (10 ** 9 + 7))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bfs(g, st, vis):
	vis[st] = st
	queue = deque([])
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.popleft()
		new.append(s)
		for i in g[s]:
			if vis[i] == -1:
				vis[i] = st
				queue.append(i)
	return vis

def var(g):
	vis = [-1] * len(g)
	curr = 0
	while curr < len(g):
		if vis[curr] != -1:
			curr += 1
			continue
		else:
			vis = bfs(g, curr, vis)
			curr += 1
	return vis

def solve():
	(n, k) = sep()
	graph = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b, c) = sep()
		if c == 1:
			continue
		a -= 1
		b -= 1
		graph[a].append(b)
		graph[b].append(a)
	diff = var(graph)
	cnt = {}
	for i in range(n):
		if diff[i] in cnt:
			cnt[diff[i]] += 1
		else:
			cnt[diff[i]] = 1
	deduct = 0
	for i in cnt:
		temp = 1
		for j in range(k):
			temp *= cnt[i]
			temp %= mod
		deduct += temp
	ans = 1
	for i in range(k):
		ans *= n
		ans %= mod
	print((ans - deduct) % mod)
testcase(1)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().split(' ')

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a, drop_zero=False):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	if drop_zero:
		return p[1:]
	else:
		return p

def prefix_mins(a, drop_zero=False):
	p = [float('inf')]
	for x in a:
		p.append(min(p[-1], x))
	if drop_zero:
		return p[1:]
	else:
		return p

def solve_a():
	n = get_int()
	s = get_str()
	cnt = 0
	for i in range(n):
		if int(s[i]) % 2 == 0:
			cnt += i + 1
	return cnt

def solve_b():
	n = get_int()
	a = get_ints()
	curr = float('inf')
	S = 0
	while a:
		curr = max(0, min(curr - 1, a.pop()))
		S += curr
	return S

class DSU:

	def __init__(self, nodes, recursive=True, choose_join=True):
		self.p = [i for i in range(nodes)]
		self.r = [0 for i in range(nodes)]
		self.s = [1 for i in range(nodes)]
		self.recursive = recursive
		self.choose_join = choose_join

	def _get_recursive(self, u):
		if u != self.p[u]:
			self.p[u] = self.get(self.p[u])
		return self.p[u]

	def _get_nonrecursive(self, u):
		v = self.p[u]
		while v != self.p[v]:
			v = self.p[v]
		while u != v:
			(u, self.p[u]) = (self.p[u], v)
		return v

	def get(self, u):
		if self.recursive:
			return self._get_recursive(u)
		else:
			return self._get_nonrecursive(u)

	def union(self, u, v):
		u = self.get(u)
		v = self.get(v)
		if u != v:
			if self.r[u] > self.r[v] and self.choose_join:
				(u, v) = (v, u)
			self.p[u] = v
			if self.r[u] == self.r[v]:
				self.r[v] += 1
			self.s[v] += self.s[u]

def solve_c():
	(n, k) = get_ints()
	M = 10 ** 9 + 7
	D = DSU(n)
	for _ in range(n - 1):
		(u, v, x) = get_ints()
		if x == 0:
			D.union(u - 1, v - 1)
	good = pow(n, k, M)
	for i in range(n):
		if D.get(i) == i:
			good -= pow(D.s[i], k, M)
			good %= M
	return good
print(solve_c())


from collections import defaultdict
from collections import deque
mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
d = defaultdict(list)
for i in range(n - 1):
	(u, v, t) = map(int, input().split())
	if t == 0:
		d[u].append(v)
		d[v].append(u)
visited = {}
ans = 0
for i in d:
	if visited.get(i, 0) == 0:
		x = 1
		visited[i] = 1
		q = deque()
		q.append(i)
		while q:
			j = q.popleft()
			for m in d[j]:
				if visited.get(m, 0) == 0:
					visited[m] = 1
					q.append(m)
					x = x + 1
		ans = (ans + pow(x, k, mod)) % mod
b = n - len(d)
ans = (pow(n, k, mod) - ans) % mod
ans = (ans - b) % mod
print(ans)


(n, k) = [int(i) for i in input().split()]
pre = [i for i in range(n)]
sz = [1 for i in range(n)]
mod = 10 ** 9 + 7

def get_pre(i):
	if i == pre[i]:
		return i
	pre[i] = get_pre(pre[i])
	return pre[i]

def merge(i, j):
	i = get_pre(i)
	j = get_pre(j)
	if i == j:
		return 0
	if sz[i] < sz[j]:
		(i, j) = (j, i)
	pre[j] = i
	sz[i] += sz[j]

def bp(a, n):
	if n == 0:
		return 1
	if n & 1 == 1:
		return a * bp(a * a % mod, n // 2) % mod
	return bp(a * a % mod, n // 2)
ans = bp(n, k)
for i in range(n - 1):
	[x, y, t] = [int(i) for i in input().split()]
	if t == 0:
		merge(x - 1, y - 1)
for i in range(n):
	if pre[i] == i:
		ans -= bp(sz[i], k)
ans %= mod
ans += mod
ans %= mod
print(ans)


(n, k) = map(int, input().split())
tr = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, x) = map(int, input().split())
	if x == 0:
		tr[a - 1].append(b - 1)
		tr[b - 1].append(a - 1)
seq = []
v = [False for i in range(n)]
for i in range(n):
	if v[i]:
		continue
	m = []
	s = [i]
	while s:
		x = s.pop()
		m.append(x)
		v[x] = True
		for y in tr[x]:
			if v[y]:
				continue
			s.append(y)
	seq.append(len(m))
ans = 0
mod = 10 ** 9 + 7
for i in seq:
	ans = ans + pow(i, k, mod)
print((pow(n, k, mod) - ans) % mod)


import sys

def dfs(start):
	global array, size
	queue = []
	queue.append(start)
	used[start] = 1
	while len(queue):
		curr = queue.pop()
		for i in range(len(array[curr])):
			if not used[array[curr][i]]:
				queue.insert(0, array[curr][i])
				size += 1
				used[array[curr][i]] = 1
try:
	(n, k) = [int(s) for s in input().split()]
	array = [[] for i in range(n)]
	used = [0] * n
	for i in range(n - 1):
		(u, v, num) = [int(s) for s in input().split()]
		if num == 1:
			continue
		u -= 1
		v -= 1
		if not u in array[v]:
			array[v].append(u)
		if not v in array[u]:
			array[u].append(v)
	ans = n ** k
	for i in range(n):
		if not used[i]:
			size = 1
			dfs(i)
			ans -= size ** k
	print(ans % (10 ** 9 + 7))
except Exception as e:
	print(e)


from collections import defaultdict
MOD = 1000000000 + 7

def power(a, b):
	result = 1
	while b > 0:
		if b % 2 == 1:
			result = result * a % MOD
		b = b // 2
		a = a * a % MOD
	return result
(n, k) = map(int, input().split(' '))
d = {}
d = defaultdict(lambda : [], d)
for _ in range(n - 1):
	(u, v, x) = map(int, input().split(' '))
	if x == 0:
		d[u].append(v)
		d[v].append(u)
vis = [0] * (n + 1)

def dfs(node):
	td = [node]
	ans = 0
	while len(td) != 0:
		m = td.pop(0)
		if vis[m] != 0:
			continue
		vis[m] = 1
		ans += 1
		for i in d[m]:
			td.append(i)
	return ans
ans1 = []
for i in range(1, n + 1):
	num = dfs(i)
	ans1.append(num)
ans2 = 0
for i in ans1:
	ans2 += power(i, k)
print((power(n, k) - ans2) % MOD)


def power(x, y, n):
	ans = 1
	while y > 0:
		if y & 1 == 1:
			ans = ans * x % n
		x = x * x % n
		y >>= 1
	return ans

class disjoint_set:

	def __init__(self, num):
		self.array = [0] + [[i, 0, 1] for i in range(1, num + 1)]

	def union(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return False
		if self.array[a][1] > self.array[b][1]:
			self.array[b][0] = a
			self.array[a][2] += self.array[b][2]
		elif self.array[a][1] < self.array[b][1]:
			self.array[a][0] = b
			self.array[b][2] += self.array[a][2]
		else:
			self.array[a][0] = b
			self.array[b][1] += 1
			self.array[b][2] += self.array[a][2]
		return True

	def find(self, a):
		p = []
		while self.array[a][0] != a:
			p.append(a)
			a = self.array[a][0]
		for i in p:
			self.array[i][0] = a
		return a
(n, k) = map(int, input().split())
graph = disjoint_set(n)
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	if not c:
		graph.union(a, b)
s = set()
for i in range(1, n + 1):
	s.add(graph.find(i))
ans = power(n, k, 1000000000 + 7)
for i in s:
	p = graph.array[i][2]
	ans -= power(p, k, 1000000000 + 7)
print(ans % (1000000000 + 7))


from collections import deque
mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = [[] for i in range(n + 1)]
for i in range(n - 1):
	(x, y, z) = map(int, input().split())
	if z == 0:
		a[x].append(y)
		a[y].append(x)
vis = [0] * (n + 1)
q = deque([])
ans = 0
for i in range(1, n + 1):
	c = 0
	if vis[i] == 0:
		q.append(i)
		vis[i] = 1
	while q:
		p = q.popleft()
		c += 1
		for j in a[p]:
			if vis[j] == 0:
				q.append(j)
				vis[j] = 1
	ans += pow(c, k, mod)
	ans %= mod
print((pow(n, k, mod) - ans) % mod)


rr = lambda : input().strip()
rri = lambda : int(rr())
rrm = lambda : list(map(int, rr().split()))
MOD = 10 ** 9 + 7

class DSU:

	def __init__(self, N):
		self.par = list(range(N + 1))
		self.rnk = [0] * (N + 1)
		self.sz = [1] * (N + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

def solve(N, K, edges):
	graph = [[] for _ in range(N)]
	dsu = DSU(N)
	for (u, v, w) in edges:
		u -= 1
		v -= 1
		if w == 0:
			dsu.union(u, v)
	ans = pow(N, K, MOD)
	for x in range(N):
		if dsu.find(x) == x:
			ans -= pow(dsu.size(x), K, MOD)
			ans %= MOD
	return ans
for tc in range(1):
	(N, K) = rrm()
	edges = [rrm() for _ in range(N - 1)]
	print(solve(N, K, edges))


import sys
input = sys.stdin.readline

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
(n, k) = map(int, input().split())
MOD = 10 ** 9 + 7
uf = Unionfind(n)
for _ in range(n - 1):
	(u, v, x) = map(int, input().split())
	if x == 0:
		uf.unite(u - 1, v - 1)
sub = 0
roots = set((uf.root(i) for i in range(n)))
for r in roots:
	c = uf.count(r)
	sub += pow(c, k, MOD)
	sub %= MOD
print((pow(n, k, MOD) - sub) % MOD)


import sys
from sys import stdin, stdout
sys.setrecursionlimit(2 * 10 ** 5)
(n, k) = stdin.readline().strip().split(' ')
(n, k) = (int(n), int(k))
adj = [[] for i in range(n)]
visited = [0 for i in range(n)]
ver_col = [[] for i in range(n)]
for i in range(n - 1):
	(u, v, x) = stdin.readline().strip().split(' ')
	(u, v, x) = (int(u), int(v), int(x))
	if x == 0:
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
count = []

def dfs(current_vertex, parent_vertex, idd):
	count[idd] += 1
	visited[current_vertex] = 1
	arr = adj[current_vertex]
	while len(arr) > 0:
		cv = arr.pop(0)
		if visited[cv] == 0:
			count[idd] += 1
			visited[cv] = 1
			arr += adj[cv]
ctr = 0
for i in range(n):
	if visited[i] == 0:
		count.append(0)
		dfs(i, -1, len(count) - 1)
		ctr += count[-1]
		if ctr == n:
			break
mo = 10 ** 9 + 7
ans = pow(n, k, mo)
for i in count:
	ans = (ans - pow(i, k, mo)) % mo
stdout.write(str(ans) + '\n')


import math
import random
import sys
from collections import defaultdict as dd
mod = 7 + 10 ** 9
col = dd(int)
g = dd(list)
(n, k) = [int(i) for i in input().split()]

def bfs(s):
	c = 1
	q = [s]
	vis[s] = 1
	while q:
		cur = q.pop(-1)
		for i in g[cur]:
			if vis[i] == 0:
				c += 1
				q.append(i)
				vis[i] = 1
	return c
for _ in range(n - 1):
	(u, v, c) = [int(i) for i in input().split()]
	if c == 0:
		g[u].append(v)
		g[v].append(u)
ans = pow(n, k, mod)
vis = [0] * (n + 1)
for i in range(1, n + 1):
	if vis[i] == 0:
		cn = bfs(i)
		ans = (ans - pow(cn, k, mod)) % mod
print(ans % mod)


from collections import defaultdict

class UnionFind:

	def __init__(self):
		self.rank = {}
		self.leader = {}

	def __repr__(self):
		return f' Ranks : {self.rank}, leaders : {self.leader} '

	def find(self, x):
		leader = self.leader.get(x, x)
		if leader != x:
			leader = self.find(leader)
			self.leader[x] = leader
		return leader

	def getRank(self, x):
		return self.rank.get(x, 0)

	def union(self, x, y):
		leader1 = self.find(x)
		leader2 = self.find(y)
		if leader1 == leader2:
			return
		if self.getRank(leader1) > self.getRank(leader2):
			self.leader[leader2] = leader1
		elif self.getRank(leader1) < self.getRank(leader2):
			self.leader[leader1] = leader2
		else:
			self.leader[leader1] = leader2
			self.rank[leader2] = 1 + self.getRank(leader2)
(n, k) = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
uf = UnionFind()
for (u, v, x) in edges:
	if x == 0:
		uf.union(u, v)
mod = int(1000000000.0 + 7)
total = pow(n, k, mod)
clusters = defaultdict(int)
for i in range(1, n + 1):
	leader = uf.find(i)
	clusters[leader] += 1
for val in clusters.values():
	total -= pow(val, k, mod)
print(total % mod)


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n, k) = gil()
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(x, y, black) = gil()
	if not black:
		adj[x].append(y)
		adj[y].append(x)
ans = 0
vis = [0] * (n + 1)
for i in range(1, n + 1):
	if vis[i]:
		continue
	stack = [i]
	vis[i] = 1
	option = 0
	while stack:
		p = stack.pop()
		option += 1
		for c in adj[p]:
			if not vis[c]:
				stack.append(c)
				vis[c] = 1
	ans += pow(option, k, mod)
	ans %= mod
ans = pow(n, k, mod) + mod - ans
ans %= mod
print(ans)


(n, k) = map(int, input().split())
p = [i for i in range(n + 1)]
sz = [1] * (n + 1)

def par(u):
	if u == p[u]:
		return u
	p[u] = par(p[u])
	return p[u]

def merge(u, v):
	sz[par(v)] += sz[par(u)]
	p[par(u)] = par(v)
for i in range(n - 1):
	(u, v, x) = map(int, input().split())
	if not x:
		merge(u, v)
MOD = int(1000000000.0 + 7)

def mul(n, p):
	ret = 1
	while p:
		if p & 1:
			ret *= n
			ret %= MOD
		p >>= 1
		n *= n
		n %= MOD
	return ret
ans = mul(n, k)
counted = [0] * (n + 1)
for i in range(1, n + 1):
	parent = par(i)
	if counted[parent]:
		continue
	counted[parent] = 1
	ans -= mul(sz[parent], k)
	if ans < 0:
		ans += MOD
print(ans)


from sys import stdin, stdout

class UnionFind:

	def __init__(self):
		self.sets = {}
		self.sizes = {}

	def make_set(self, s):
		if s in self.sets:
			return
		else:
			self.sets[s] = s
			self.sizes[s] = 1

	def find(self, s):
		path = []
		while s != self.sets[s]:
			path.append(s)
			s = self.sets[s]
		for p in path:
			self.sets[p] = s
		return s

	def union(self, s1, s2):
		a = self.find(s1)
		b = self.find(s2)
		if a == b:
			return
		self.sets[a] = b
		self.sizes[b] += self.sizes[a]

	def num_bad(self, k):
		res = 0
		for s in self.sets:
			if s == self.sets[s]:
				res += self.sizes[s] ** k
		return res

def main():
	(n, k) = [int(x) for x in stdin.readline().split()]
	uf = UnionFind()
	for i in range(1, n + 1):
		uf.make_set(i)
	for i in range(n - 1):
		(u, v, c) = [int(x) for x in stdin.readline().split()]
		if c == 0:
			uf.union(u, v)
	print((n ** k - uf.num_bad(k)) % (10 ** 9 + 7))
main()


import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest

def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def sortListWithIndex(listOfTuples, idx):
	return sorted(listOfTuples, key=lambda x: x[idx])

def sortDictWithVal(passedDic):
	temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
	toret = {}
	for tup in temp:
		toret[tup[0]] = tup[1]
	return toret

def sortDictWithKey(passedDic):
	return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
(n, k) = MAP()
redNodes = set()
graph = defaultdict(list)
edges = defaultdict(lambda : None)
for _ in range(n - 1):
	(a, b, c) = MAP()
	if c == 0:
		redNodes.add(a)
		redNodes.add(b)
	graph[a].append(b)
	graph[b].append(a)
	edges[a, b] = c
	edges[b, a] = c
totalRed = len(redNodes)
total = pow(n, k, mod)
visited = [0] * (n + 1)
consReds = []
for i in range(1, n + 1):
	if visited[i] == False:
		stack = [i]
		numReds = 0
		while stack:
			node = stack.pop()
			visited[node] = True
			for child in graph[node]:
				if visited[child] == False:
					if edges[node, child] == 0:
						stack.append(child)
						numReds += 1
		consReds.append(numReds)
toSub = n - totalRed
for el in consReds:
	if el != 0:
		toSub += pow(el + 1, k, mod)
rem = (total - toSub) % mod
if rem < 0:
	print(mod - rem)
else:
	print(rem)


(n, k) = [int(x) for x in input().split()]
graph = {x + 1: [] for x in range(n)}
for _ in range(n - 1):
	(u, v, c) = [int(x) for x in input().split()]
	if c == 0:
		graph[u].append(v)
		graph[v].append(u)
MOD = int(1000000000.0 + 7)
explored = [False for _ in range(n + 1)]

def count(u):
	ans = 0
	stack = [u]
	while len(stack) > 0:
		u = stack.pop()
		ans += 1
		for v in graph[u]:
			if not explored[v]:
				explored[v] = True
				stack.append(v)
	return ans
invalid = 0
for i in range(1, n + 1):
	if not explored[i]:
		explored[i] = True
		c = count(i)
		invalid += pow(c, k, MOD)
		invalid %= MOD
ans = (MOD + (pow(n, k, MOD) - invalid)) % MOD
print(ans)


p = 10 ** 9 + 7
(n, k) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b, x) = map(int, input().split())
	if x != 0:
		continue
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
visited = [False] * n
m = 0
for i in range(len(g)):
	if visited[i] == True:
		continue
	d = []
	visited[i] = True
	d.append(i)
	c = 0
	while d:
		o = d.pop()
		for j in g[o]:
			if visited[j] == True:
				continue
			visited[j] = True
			d.append(j)
		c += 1
	m += pow(c, k, p)
print((pow(n, k, p) + p - m) % p)


import collections as cc
I = lambda : list(map(int, input().split()))
(n, k) = I()
mod = 10 ** 9 + 7
parent = [i for i in range(n + 1)]

def find(x):
	global count
	count += 1
	while parent[x] != x:
		x = parent[x]
	return x

def union(x, y):
	a = find(x)
	b = find(y)
	if a != b:
		parent[a] = parent[b] = min(a, b)
count = 0
tf = 0
for i in range(n - 1):
	(a, b, c) = I()
	if not c:
		tf = 1
		union(a, b)
temp = [find(i) for i in range(1, n + 1)]
tem = cc.Counter(temp)
ans = pow(n, k, mod)
for i in tem:
	ans -= tem[i] ** k % mod
	ans %= mod
print(ans)


from collections import defaultdict as dd
(n, k) = map(int, input().strip().split())
graph = dd(list)

def bfs(a):
	visited[a] = 1
	arr = [a]
	ct = 1
	while arr:
		b = arr.pop(0)
		for i in graph[b]:
			if visited[i] == 0:
				visited[i] = 1
				arr.append(i)
				ct += 1
	return ct
for i in range(n - 1):
	(a, b, c) = map(int, input().strip().split())
	if c == 0:
		graph[a].append(b)
		graph[b].append(a)
visited = [0] * (n + 1)
mod = 10 ** 9 + 7
tot = pow(n, k, mod)
for i in range(1, n + 1):
	if visited[i] == 0:
		w = bfs(i)
		tot = (tot - pow(w, k, mod)) % mod
print(tot % mod)


def read_line():
	return list(map(int, input().split()))
mod = 1000000007
g = {}
(n, k) = read_line()
done = set()
curr = 1
count = 0
for _ in range(n - 1):
	(u, v, x) = read_line()
	if x == 0:
		li = g.get(u, [])
		li.append(v)
		g[u] = li
		li = g.get(v, [])
		li.append(u)
		g[v] = li

def width_search(n):
	comp = 0
	q = []
	q.append(n)
	done.add(n)
	while q:
		x = q.pop(0)
		comp += 1
		l = g.get(x, [])
		for i in l:
			if i not in done:
				q.append(i)
				done.add(i)
	return comp
answer = n ** k
for i in range(1, n + 1):
	if i not in done:
		answer -= width_search(i) ** k
print(str(answer % mod))


from collections import defaultdict
M = 10 ** 9 + 7

class Graph:

	def __init__(self, n, k):
		self.red = defaultdict(list)
		self.black = defaultdict(list)
		self.visitedRed = defaultdict(bool)
		self.vertices = n
		self.power = k
		self.minus = 0
		self.blackPowerNegative = 0

	def addEdge(self, fr, to, col):
		if col == 0:
			self.red[fr].append(to)
			self.red[to].append(fr)
		else:
			self.black[fr].append(to)
			self.black[to].append(fr)

	def BFSUtil(self, root):
		count = 0
		if len(self.red[root]) == 0:
			return
		queue = [root]
		self.visitedRed[root] = True
		while queue:
			s = queue.pop(0)
			count += 1
			for k in self.red[s]:
				if self.visitedRed[k] == False:
					self.visitedRed[k] = True
					queue.append(k)
		self.minus += pow(count, self.power, M)

	def BFS(self):
		for i in range(1, self.vertices + 1):
			if self.visitedRed[i] == False:
				self.BFSUtil(i)

	def BFSBlack(self):
		for i in self.black.keys():
			if not self.red[i]:
				self.blackPowerNegative += 1

	def solve(self):
		X = (pow(self.vertices, self.power, M) - self.minus) % M - self.blackPowerNegative
		print(X)
(n, k) = map(int, input().split())
G = Graph(n, k)
for i in range(n - 1):
	(a, b, col) = [int(x) for x in input().split()]
	G.addEdge(a, b, col)
G.BFS()
G.BFSBlack()
G.solve()


import sys
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
mod = 10 ** 9 + 7
(n, k) = Ri()
par = [i for i in range(n)]
rank = [1 for i in range(n)]
cc = n

def find(x):
	if par[x] == x:
		return x
	temp = find(par[x])
	par[x] = temp
	return temp

def union(a, b):
	par[b] = a
	rank[a] += rank[b]
s = set([i for i in range(n)])
bedge = set([i for i in range(n)])
for _ in range(n - 1):
	(a, b, x) = Ri()
	a -= 1
	b -= 1
	if x == 0:
		pa = find(a)
		pb = find(b)
		if pa != pb:
			s.remove(pb)
			union(pa, pb)
			cc -= 1
			if a in bedge:
				bedge.remove(a)
			if b in bedge:
				bedge.remove(b)
dif = 0
ans = 0
tot = 0
for i in s:
	if rank[i] > 1:
		dif += pow(rank[i], k, mod)
		dif = dif % mod
print((pow(n, k, mod) - dif - len(bedge)) % mod)


import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
MOD = 1000000007
(n, power) = map(int, stdin.readline().split())
graph = defaultdict(lambda : [])
for _ in range(n - 1):
	(u, v, x) = map(int, stdin.readline().split())
	graph[u].append([v, x])
	graph[v].append([u, x])
ans = pow(n, power, MOD)
visited = [False] * (n + 1)
for i in range(1, n + 1):
	if not visited[i]:
		visited[i] = True
		count = 0
		q = deque()
		q.append(i)
		while len(q) > 0:
			temp = q.popleft()
			count += 1
			for (j, k) in graph[temp]:
				if not visited[j] and k == 0:
					visited[j] = True
					q.append(j)
		ans -= pow(count, power, MOD)
print(ans % MOD)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 6)

def explore(adj, i):
	visited[i] = 1
	count = 1
	for j in adj[i]:
		if visited[j] != 1:
			count += explore(adj, j)
	return count
(n, k) = invr()
adj = [[] for i in range(n)]
x = 0
for i in range(n - 1):
	(a, b, c) = invr()
	if c == 0:
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	else:
		x += 1
visited = [0 for i in range(n)]
ans = 0
if x != 0:
	for i in range(n):
		if visited[i] == 0:
			count = explore(adj, i)
			ans += pow(count, k, 1000000007)
	print((pow(n, k, 1000000007) - ans % 1000000007) % 1000000007)
else:
	print(0)


class UnionFind:

	def __init__(self, n):
		self.sz = [-1 for i in range(n)]

	def find(self, x):
		if self.sz[x] < 0:
			return x
		else:
			self.sz[x] = self.find(self.sz[x])
			return self.sz[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return False
		if self.sz[x] > self.sz[y]:
			(x, y) = (y, x)
		self.sz[x] += self.sz[y]
		self.sz[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.sz[self.find(x)]
MOD = 10 ** 9 + 7
(N, k) = map(int, input().split())
uf = UnionFind(N)
for i in range(N - 1):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	if c == 0:
		uf.union(a, b)
ans = N ** k % MOD
l = [0] * N
for i in range(N):
	l[i] = uf.find(i)
for a in list(set(l)):
	if a == -1:
		continue
	ans -= uf.size(a) ** k
	ans %= MOD
ans -= l.count(-1)
print(ans % MOD)


import sys

def readLine():
	return [int(i) for i in input().split()]

def deg(x, y):
	if y == 1:
		return x
	res = deg(x, y // 2)
	res *= res
	res %= md
	if y % 2 == 1:
		res *= x
		res %= md
	return res

def dfs(v):
	Q = [v]
	used[v] = True
	c = 0
	while Q:
		v = Q.pop()
		c += 1
		for to in g[v]:
			if not used[to]:
				used[to] = True
				Q.append(to)
	return c
(n, m) = readLine()
g = [[] for _ in range(n + 1)]
md = 1000000007
for i in range(n - 1):
	(x, y, t) = readLine()
	if t == 0:
		g[x].append(y)
		g[y].append(x)
ans = deg(n, m)
used = [False] * (n + 1)
for i in range(1, n + 1):
	if used[i] == False:
		b = dfs(i)
		ans = ans - deg(b, m)
		if ans < 0:
			ans += md
print(ans)


from collections import defaultdict as dd

def dfs(s, tree, visited):
	stack = []
	if s not in visited:
		stack.append(s)
	ccsize = 0
	while stack:
		v = stack.pop()
		ccsize += 1
		if v not in visited:
			visited.add(v)
		for n in tree[v]:
			if n not in visited:
				stack.append(n)
	return ccsize

def read_input():
	return [int(i) for i in input().split()]
(n, k) = read_input()
total = n ** k
final = 10 ** 9 + 7
tree = dd(list)
for i in range(n - 1):
	(u, v, c) = read_input()
	if c == 0:
		tree[u].append(v)
		tree[v].append(u)
count_bad = 0
visited = set()
for i in range(1, n + 1):
	count_bad = count_bad % final + dfs(i, tree, visited) ** k % final
print((total % final - count_bad % final + final) % final)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
sys.setrecursionlimit(111111)
INF = 99999999999999999999999999999999

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, k) = ria()
		graph = [[] for i in range(n + 1)]
		visited = [False] * (n + 1)
		for i in range(n - 1):
			(a, b, type) = ria()
			if type == 0:
				graph[a].append(b)
				graph[b].append(a)

		def dfs(start):
			stack = [start]
			cs = 0
			while stack:
				start = stack[-1]
				if not visited[start]:
					cs += 1
					visited[start] = True
					for child in graph[start]:
						if not visited[child]:
							stack.append(child)
				else:
					stack.pop()
			return cs
		nk = 1
		for i in range(k):
			nk = n * nk % mod
		for i in range(1, n + 1):
			if not visited[i]:
				cs = dfs(i)
				rem = 1
				for i in range(k):
					rem = cs * rem % mod
				nk -= rem
		print(nk % mod)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


from collections import defaultdict

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def BFS(self, s):
		path = []
		d2 = {}
		queue = []
		queue.append(s)
		d2[s] = 1
		while queue:
			s = queue.pop(0)
			path.append(s)
			for i in self.graph[s]:
				if i not in d2:
					queue.append(i)
					d2[i] = 1
		return path
(n, k) = map(int, input().split())
g = Graph()
d1 = {}
l1 = []
x = 0
for i in range(0, n - 1):
	(a, b, c) = map(int, input().split())
	x = max(a, b, x)
	if c == 0:
		if a not in d1:
			l1.append(a)
			d1[a] = 1
		if b not in d1:
			l1.append(b)
			d1[b] = 1
		g.addEdge(a, b)
		g.addEdge(b, a)
l3 = []
for item in l1:
	l2 = []
	if item in d1:
		l2 = g.BFS(item)
		l3.append(len(l2))
		for item in l2:
			del d1[item]
ans = pow(x, k, 10 ** 9 + 7)
f = 0
for item in l3:
	f += item
	ans -= pow(item, k, 10 ** 9 + 7)
	ans = ans % (10 ** 9 + 7)
print(ans - (x - f))