Sắp tới đây bạn được đại diện cho Việt Nam đi tham gia bầu cử chủ tịch Liên Hợp Quốc

Bạn sẽ đi từ Việt Nam đến Mỹ bằng máy bay, bạn muốn tìm câu trả lời cho những câu hỏi sau:

\(1\). Giá tối thiểu của một tuyến đường như vậy là gì?

\(2\). Có bao nhiêu tuyến đường giá tối thiểu?

\(3\). Số lượng chuyến bay tối thiểu với tuyến giá tối thiểu là bao nhiêu?

\(4\). Số lượng chuyến bay tối đa với tuyến giá tối thiểu là bao nhiêu?

Đầu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\), số quốc gia và số chuyến bay. Các quốc gia được đánh số \(1,2,…,n\). Quốc gia \(1\) là Việt Nam, và Quốc gia \(n\) là Mỹ.

Tiếp theo, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng chứa ba số nguyên \(a, b, c\) : có một chuyến bay từ quốc gia \(a\) đến quốc gia \(b\) với giá \(c\). Tất cả các chuyến bay đều là chuyến bay một chiều.

Đầu ra

Bốn số nguyên theo những câu hỏi trên lấy dư \(1000000007\).

Giới hạn

\(1 ≤ n ≤ 10^5\)

\(1 ≤ m ≤ 2*10^5\)

\(1 ≤ a , b ≤ n\)

\(1 ≤ c ≤ 10^9\)

Ví dụ:

Đầu vào:

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

Đầu ra:

5 2 1 2