We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Toll Cost Digits

Toll Cost Digits

The mayor of Farzville is studying the city's road system to find ways of improving its traffic conditions. Farzville's road system consists of junctions connected by bidirectional toll roads, where the toll road connects junctions and . In addition, some junctions may not be reachable from others and there may be multiple roads connecting the same pair of junctions.

Each toll road has a toll rate that's paid each time it's used. This rate varies depending on the direction of travel:

  • If traveling from to , then the toll rate is .
  • If traveling from to , then the toll rate is . It is guaranteed that .

image

For each digit , the mayor wants to find the number of ordered pairs of junctions such that and a path exists from to where the total cost of the tolls (i.e., the sum of all toll rates on the path) ends in digit . Given a map of Farzville, can you help the mayor answer this question? For each digit from to , print the the number of valid ordered pairs on a new line.

Note: Each toll road can be traversed an unlimited number of times in either direction.

Input Format

The first line contains two space-separated integers describing the respective values of (the number of junctions) and (the number of roads).
Each line of the subsequent lines describes a toll road in the form of three space-separated integers, , , and .

Constraints

Output Format

Print ten lines of output. Each line (where ) must contain a single integer denoting the answer for . For example, the first line must contain the answer for , the second line must contain the answer for , and so on.

Sample Input 0

3 3
1 3 602
1 2 256
2 3 411

Sample Output 0

0
2
1
1
2
0
2
1
1
2

Explanation 0

The table below depicts the distinct pairs of junctions for each :

Note the following:

  • There may be multiple paths between each pair of junctions.
  • Junctions and roads may be traversed multiple times. For example, the path is also valid, and it has total cost of .
  • An ordered pair can be counted for more than one . For example, the pair is counted for and .
  • Each ordered pair must only be counted once for each . For example, the paths and both have total costs that end in , but the pair is only counted once.