Hệ Thống Kênh

Một hệ thống máy chủ cần gửi gói dữ liệu từ nút nguồn $1$ đến nút đích $N$. Hệ thống bao gồm $N$ nút xử lý và $M$ kênh kết nối giữa các nút này. Có hai loại kênh: kênh một chiều và kênh hai chiều. Mỗi kênh kết nối có độ dài truyền tải là một số nguyên dương.

Hãy xác định độ dài truyền tải ngắn nhất từ nút $1$ đến nút $N$, đồng thời đếm số lượng đường truyền ngắn nhất khác nhau từ nút $1$ đến nút $N$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 ≤ N ≤ 5000$, $1 ≤ M ≤ 20000$), lần lượt là số lượng nút xử lý và số lượng kênh kết nối.

$M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $K, U, V, L$ ($K \in {1, 2}$, $1 ≤ U, V ≤ N$, $1 ≤ L ≤ 32000$) mô tả một kênh kết nối:

• Nếu $K = 1$, có một kênh một chiều truyền từ nút $U$ đến nút $V$ với độ dài $L$.
• Nếu $K = 2$, có một kênh hai chiều kết nối giữa nút $U$ và nút $V$ với độ dài $L$.

Kết quả

In ra hai số nguyên cách nhau bởi một khoảng trắng: số thứ nhất là độ dài truyền tải ngắn nhất, số thứ hai là số lượng đường truyền ngắn nhất thỏa mãn.

Chấm điểm

Subtask 1 (20 points). $N ≤ 8$; $M ≤ 15$

Subtask 2 (30 points). Đồ thị là DAG với các cạnh hướng từ U đến V thỏa mãn $U < V$

Subtask 3 (50 points). $1 ≤ N ≤ 5000$; $1 ≤ M ≤ 20000$

Ví dụ

Input

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

Output

3 2

Ghi chú

Dữ liệu đảm bảo số lượng đường truyền ngắn nhất không vượt quá giới hạn của số nguyên 64-bit có dấu.