```go
package main

import (
	"fmt"
	"io"
	"os"
	"sort"
)

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

func modInverse(a, m int64) int64 {
	_, x, _ := extGCD(a, m)
	return (x%m + m) % m
}

type Edge struct {
	to, weight int
}

type PathData struct {
	valUp  int64
	target int64
}

func countPairs(data []PathData) int64 {
	if len(data) == 0 {
		return 0
	}
	sort.Slice(data, func(i, j int) bool {
		return data[i].valUp < data[j].valUp
	})
	var total int64
	for _, d := range data {
		t := d.target
		
		l, r := 0, len(data)
		for l < r {
			m := l + (r-l)/2
			if data[m].valUp >= t {
				r = m
			} else {
				l = m + 1
			}
		}
		left := l
		
		l, r = 0, len(data)
		for l < r {
			m := l + (r-l)/2
			if data[m].valUp > t {
				r = m
			} else {
				l = m + 1
			}
		}
		right := l
		
		total += int64(right - left)
	}
	return total
}

func main() {
	buffer, err := io.ReadAll(os.Stdin)
	if err != nil && err != io.EOF {
		return
	}
	pos := 0
	readInt := func() int {
		for pos < len(buffer) && buffer[pos] <= ' ' {
			pos++
		}
		if pos >= len(buffer) {
			return 0
		}
		res := 0
		for pos < len(buffer) && buffer[pos] > ' ' {
			res = res*10 + int(buffer[pos]-'0')
			pos++
		}
		return res
	}

	n := readInt()
	if n == 0 {
		return
	}
	M := int64(readInt())

	if M == 1 {
		fmt.Println(int64(n) * int64(n-1))
		return
	}

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

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

	sz := make([]int, n)
	removed := make([]bool, n)

	var getSizes func(u, p int) int
	getSizes = func(u, p int) int {
		sz[u] = 1
		for _, e := range graph[u] {
			if e.to != p && !removed[e.to] {
				sz[u] += getSizes(e.to, u)
			}
		}
		return sz[u]
	}

	var getCentroid func(u, p, total int) int
	getCentroid = func(u, p, total int) int {
		for _, e := range graph[u] {
			if e.to != p && !removed[e.to] && sz[e.to] > total/2 {
				return getCentroid(e.to, u, total)
			}
		}
		return u
	}

	var collect func(u, p, length int, valUp, valDown int64, res *[]PathData)
	collect = func(u, p, length int, valUp, valDown int64, res *[]PathData) {
		target := (M - valDown) % M
		target = (target * invPow10[length]) % M
		*res = append(*res, PathData{valUp, target})
		for _, e := range graph[u] {
			if e.to != p && !removed[e.to] {
				nLen := length + 1
				nValUp := (int64(e.weight)*pow10[length] + valUp) % M
				nValDown := (valDown*10 + int64(e.weight)) % M
				collect(e.to, u, nLen, nValUp, nValDown, res)
			}
		}
	}

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

		compData := make([]PathData, 0, total)
		compData = append(compData, PathData{0, 0})

		for _, e := range graph[centroid] {
			if !removed[e.to] {
				nLen := 1
				nValUp := int64(e.weight) % M
				nValDown := int64(e.weight) % M
				startIdx := len(compData)
				collect(e.to, centroid, nLen, nValUp, nValDown, &compData)
				ans -= countPairs(compData[startIdx:])
			}
		}

		ans += countPairs(compData)
		ans -= 1

		removed[centroid] = true
		for _, e := range graph[centroid] {
			if !removed[e.to] {
				solve(e.to)
			}
		}
	}

	solve(0)
	fmt.Println(ans)
}
```