Điều tra đường bay (Investigation)

Nguồn: CSES Problem Set

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ thành phố và $m$ chuyến bay một chiều. Chuyến bay từ $a$ đến $b$ có giá $c>0$.

Bạn cần đi từ thành phố $1$ đến thành phố $n$. Hãy xác định đồng thời:

1. chi phí nhỏ nhất của một tuyến;
2. số tuyến có chi phí nhỏ nhất, lấy modulo $10^9+7$;
3. số chuyến bay ít nhất trong một tuyến có chi phí nhỏ nhất;
4. số chuyến bay nhiều nhất trong một tuyến có chi phí nhỏ nhất.

Đề bảo đảm tồn tại ít nhất một tuyến từ thành phố $1$ đến thành phố $n$.

Input

Dòng đầu chứa hai số nguyên $n,m$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa $a,b,c$, mô tả một chuyến bay một chiều từ $a$ đến $b$ có giá $c$.

Output

In bốn số theo thứ tự: chi phí nhỏ nhất, số tuyến có chi phí nhỏ nhất modulo $10^9+7$, số chuyến bay ít nhất và số chuyến bay nhiều nhất trong các tuyến tối ưu.

Subtask

Trong tất cả các Subtask: $1\le a,b\le n$; $1\le c\le10^9$; luôn tồn tại đường đi từ $1$ đến $n$.

• Subtask 1 — 20% — 0.30 giây: $1\le n\le100$; $1\le m\le500$.
• Subtask 2 — 30% — 0.60 giây: $1\le n\le5000$; $1\le m\le10^4$.
• Subtask 3 — 50% — 1.00 giây: $1\le n\le10^5$; $1\le m\le2\cdot10^5$.

Ví dụ

Input

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

Output

5 2 1 2

Giải thích

Chi phí nhỏ nhất là $5$. Có hai đường đạt chi phí này: cạnh trực tiếp $1\to4$ và đường $1\to3\to4$. Vì vậy số đường là $2$, số chuyến ít nhất là $1$ và nhiều nhất là $2$.