Description

The staff at the “RP Restaurant” are quite something. After unanimously calculating the same phone number, they are about to send HZH and TZY to deliver takeout. They drew a map of their city. On this map, there are $N$ locations. They are currently at the town labeled “1,” and the delivery destination is the town labeled “N.” In addition, all roads are one-way. The time cost from town $I$ to town $J$ is $D[I, J]$. To deliver the food more efficiently, they want to take a route from town $1$ to town $N$ with the minimal cost. However, just before departure, they bumped into FYY, who was angry due to a traffic jam, and were inspired: it is not enough to know only one route. So, they invited FYY to study the next problem together: how many minimal-cost paths are there?

Input Format

The first line contains two space-separated integers $N, E$, indicating the number of towns and the number of edges in the map.

Each of the next $E$ lines contains three integers $I, J, C$, meaning there is a directed road from town $I$ to town $J$ with cost $C$. Note that edge records in the testdata may be duplicated, but it is guaranteed that $I \ne J$ and $1 \leq I, J \leq N$.

Output Format

Output two numbers: the minimal cost and the total number of minimal-cost paths. It is guaranteed that the total number of minimal-cost paths does not exceed $2^{30}$.

Two shortest path solutions are considered different if their path lengths are equal (both are the shortest path length) and the sequences of node indices visited on the shortest paths are different.

If city $N$ is unreachable, output only No answer.

5 4
1 5 4
1 2 2
2 5 2
4 1 1

4 2

Hint

• For $30\%$ of the testdata, $N \leq 20$.
• For $100\%$ of the testdata, $1 \leq N \leq 2000$, $0 \leq E \leq N \times (N - 1)$, $1 \leq C \leq 10$.

Translated by ChatGPT 5