Marisa đang chơi một trò chơi điện tử, nhiệm vụ của Marisa là cai quản vương quốc của mình. Cho biết, vương quốc của Marisa bao gồm $n$ pháo đài được kết nối bởi $m$ con đường hai chiều,con đường thứ $i$ kết nối giữa pháo đài $u_i,v_i$ và có độ dài $w_i$. Pháo đài có cổng vào là pháo đài $1$ và pháo đài chính là pháo đài $n$. Biết rằng giữa hai pháo đài có thể có nhiều con đường và một pháo đài có thể có con đường nối đến chính nó. Mỗi lượt chơi, quân địch sẽ tấn công vương quốc của Marisa, quân địch sẽ tiến vào từ pháo đài $1$ (nơi có cổng vào) và mục tiêu của chúng là tiến tới pháo đài chính (pháo đài thứ $n$) .Cho biết quân địch luôn đi theo đường đi ngắn nhất. Marisa đề ra chiến thuật rằng quân lính của mình sẽ tập trung ở pháo đài chính $n$ và chờ quân địch đến để tấn công.Để có nhiều thời gian chuẩn bị cho việc phòng thủ, Marisa muốn tổng quãng đường quân địch đi từ pháo đài $1$ đến pháo đài $n$ là lớn nhất vì chúng sẽ mất nhiều thời gian di chuyển hơn. Chính vì vậy, Marisa sẽ phá huỷ duy nhất một con đường để đạt được mục tiêu của mình. Ngoài ra hãy giúp Marisa đếm số cách để phá huỷ các con đường sao cho thoả mãn yêu cầu đề ra.
### Input
- Dòng thứ nhất chứa $2$ số nguyên dương $n,m.$
- $m$ dòng tiếp theo, dòng thứ $i$ chứa $3$ số nguyên dương $u_i,v_i,w_i.$
### Output
- In ra hai số nguyên $dis,cnt$ với $dis$ là khoảng cách dài nhất mà quân địch phải đi sau khi phá huỷ một con đường và $cnt$ là số cách phá huỷ để đạt được điều đó.
### Điều kiện
- $1 \le n \le 10^5,1 \le m \le 2 \cdot 10^5.$
- $1 \le w_i \le 10^4$ với mọi $1 \le i \le m.$
- Dữ liệu đảm bảo tồn tại đường đi từ pháo đài $1$ đến pháo đài $n$ trong vương quốc ban đầu và sau khi phá huỷ một con đường bất kỳ.
### Ví dụ
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
```
