Khám phá đảo động vật

Trong một chuyến phiêu lưu, bạn tình cờ khám phá ra một hòn đảo bí ẩn nơi các loài động vật sinh sống. Đảo này được phân chia thành nhiều khu vực khác nhau, mỗi khu vực có thể nối với một hoặc nhiều khu vực khác thông qua các con đường. Mỗi con đường có độ dài khác nhau và có thể là một chiều hoặc hai chiều.

Từ khu vực đầu tiên trên đảo, bạn muốn tìm ra con đường nhanh nhất để đến khu vực cuối cùng, nơi bạn sẽ gặp một loài động vật quý hiếm. Tuy nhiên, bạn cũng muốn biết có bao nhiêu lộ trình ngắn nhất từ khu vực đầu đến khu vực cuối.

Để giúp bạn, bài toán yêu cầu bạn tìm ra độ dài ngắn nhất của con đường và số lượng các con đường ngắn nhất có thể đi từ khu vực đầu tiên đến khu vực cuối cùng.

Input

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \leq N \leq 5000, 1 \leq M \leq 31313)\), tương ứng với số lượng khu vực và số lượng con đường trên đảo.

M dòng tiếp theo mô tả các con đường nối các khu vực. Mỗi con đường được mô tả bằng 4 số nguyên \(K, U, V, L\):

• Nếu \(K = 1\), con đường là một chiều từ \(U\) đến \(V\) có độ dài \(L\).

• Nếu \(K = 2\), con đường là hai chiều nối \(U\) với \(V\) có độ dài \(L\) (tức là có đường đi từ \(U\) đến \(V\) và ngược lại).

Output

In ra hai số nguyên:

1. Độ dài ngắn nhất của con đường từ khu vực đầu tiên đến khu vực cuối cùng.

2. Số lượng các con đường ngắn nhất có thể đi từ khu vực đầu tiên đến khu vực cuối cùng.

Example

3 2
1 1 2 3
2 2 3 1

4
1