Marisa is playing a video game where her mission is to manage her kingdom. Marisa's kingdom consists of $n$ fortresses connected by $m$ two-way roads. The $i$-th road connects fortress $u_i$ and $v_i$ and has a length of $w_i$. The entrance to the kingdom is located at fortress $1$, and the main fortress is fortress $n$. It is known that: There can be multiple roads between two fortresses and a fortress may have a road connecting to itself. In each round of the game, enemies will attack Marisa's kingdom. The enemies will enter from fortress $1$ (the entrance) and aim to reach the main fortress (fortress $n$). It is given that the enemies always follow the shortest path. Marisa has devised a strategy where her soldiers will concentrate at the main fortress $n$ and wait to attack the enemies when they arrive. To have more time to prepare for defense, Marisa wants the total distance the enemies travel from fortress $1$ to fortress $n$ to be as large as possible, as it will take the enemies more time to move. To achieve this goal, Marisa will destroy exactly one road. Additionally, help Marisa count the number of ways she can destroy the roads to meet this requirement.
### Input
- The first line contains 2 positive integers $n, m$.
- The next $m$ lines, the $i^{\text{th}}$ line, contains 3 positive integers $u_i, v_i, w_i$.
### Output
Print two integers, $dis$ and $cnt$, where:
- $dis$ is the longest distance the enemy must travel after destroying one road.
- $cnt$ is the number of ways to destroy roads to achieve $dis$.
### Constraints
- $1 \leq n \leq 10^5, 1 \leq m \leq 2 \cdot 10^5$
- $1 \leq w_i \leq 10^4$ for all $1 \leq i \leq m$
The data guarantees that there is a path from fortress $1$ to fortress $n$ initially and after removing any one road.
### Example
Input:
```
3 4
1 2 2
1 2 4
2 3 2
2 3 4
```
Output:
```
6 2
```
Input:
```
5 7
2 2 3
1 3 4
2 4 9
3 4 10
4 5 7
1 2 8
2 5 16
```
Output:
```
24 3
```
