```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var scanner *bufio.Scanner

func init() {
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, bufio.MaxScanTokenSize)
}

func nextInt() int {
	scanner.Scan()
	res := 0
	for _, b := range scanner.Bytes() {
		res = res*10 + int(b-'0')
	}
	return res
}

type Edge struct {
	to, weight int
}

type Node struct {
	up, down, d int
}

var (
	M       int
	pow10   []int64
	inv10   []int64
	ans     int64
	adj     [][]Edge
	deleted []bool
	sz      []int
)

func extGCD(a, b int64) (int64, int64, int64) {
	if b == 0 {
		return a, 1, 0
	}
	gcd, x1, y1 := extGCD(b, a%b)
	x := y1
	y := x1 - (a/b)*y1
	return gcd, x, y
}

func modInverse(n, m int64) int64 {
	if m == 1 {
		return 0
	}
	_, x, _ := extGCD(n, m)
	return (x%m + m) % m
}

func getSizes(u, p int) int {
	sz[u] = 1
	for _, edge := range adj[u] {
		v := edge.to
		if v != p && !deleted[v] {
			sz[u] += getSizes(v, u)
		}
	}
	return sz[u]
}

func getCentroid(u, p, total int) int {
	for _, edge := range adj[u] {
		v := edge.to
		if v != p && !deleted[v] && sz[v] > total/2 {
			return getCentroid(v, u, total)
		}
	}
	return u
}

func dfs(u, p, d, up, down int, list *[]Node) {
	*list = append(*list, Node{up, down, d})
	for _, edge := range adj[u] {
		v := edge.to
		if v != p && !deleted[v] {
			w := edge.weight
			nextD := d + 1
			nextUp := int((int64(w)*pow10[d] + int64(up)) % int64(M))
			nextDown := int((int64(down)*10 + int64(w)) % int64(M))
			dfs(v, u, nextD, nextUp, nextDown, list)
		}
	}
}

func count(list []Node) int {
	ups := make([]int, len(list))
	for i, item := range list {
		ups[i] = item.up
	}
	sort.Ints(ups)

	res := 0
	for _, item := range list {
		val := (int64(-item.down) * inv10[item.d]) % int64(M)
		if val < 0 {
			val += int64(M)
		}
		target := int(val)

		l := sort.SearchInts(ups, target)
		if l < len(ups) && ups[l] == target {
			r := sort.SearchInts(ups, target+1)
			res += r - l
		}
	}
	return res
}

func solve(u int) {
	total := getSizes(u, -1)
	centroid := getCentroid(u, -1, total)

	listAll := make([]Node, 0, total)
	listAll = append(listAll, Node{0, 0, 0})

	for _, edge := range adj[centroid] {
		v := edge.to
		if !deleted[v] {
			listV := make([]Node, 0)
			nextD := 1
			nextUp := edge.weight % M
			nextDown := edge.weight % M
			dfs(v, centroid, nextD, nextUp, nextDown, &listV)

			ans -= int64(count(listV))
			listAll = append(listAll, listV...)
		}
	}

	ans += int64(count(listAll))
	ans -= 1

	deleted[centroid] = true
	for _, edge := range adj[centroid] {
		v := edge.to
		if !deleted[v] {
			solve(v)
		}
	}
}

func main() {
	n := nextInt()
	M = nextInt()

	pow10 = make([]int64, n+1)
	inv10 = make([]int64, n+1)
	pow10[0] = 1
	inv10[0] = 1
	inv10_1 := modInverse(10, int64(M))
	for i := 1; i <= n; i++ {
		pow10[i] = (pow10[i-1] * 10) % int64(M)
		inv10[i] = (inv10[i-1] * inv10_1) % int64(M)
	}

	adj = make([][]Edge, n)
	for i := 0; i < n-1; i++ {
		u := nextInt()
		v := nextInt()
		w := nextInt()
		adj[u] = append(adj[u], Edge{v, w})
		adj[v] = append(adj[v], Edge{u, w})
	}

	deleted = make([]bool, n)
	sz = make([]int, n)

	solve(0)

	fmt.Println(ans)
}
```