Điều Tra

Có $n$ thành phố và $m$ chuyến bay một chiều. Tìm bốn thông tin về đường đi từ thành phố $1$ đến thành phố $n$: (1) chi phí nhỏ nhất, (2) số đường đi có chi phí nhỏ nhất (modulo ${10}^9+7$), (3) số chuyến bay ít nhất trong một đường đi tối ưu, (4) số chuyến bay nhiều nhất trong một đường đi tối ưu.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$, $b$, $c$ — chuyến bay từ $a$ đến $b$ với chi phí $c$.

Dữ liệu ra

In bốn số nguyên trên một dòng.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 2\times {10}^5$
• $1\le c\le {10}^9$

Ví dụ