Đến trường

Điểm: 0,11 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Nguyễn Minh Hiếu

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ngày 27/11 tới là ngày tổ chức thi học kỳ $I$ ở trường ĐH BK. Là sinh viên năm thứ nhất, Hiếu không muốn vì đi muộn mà gặp trục trặc ở phòng thi nên đã chuẩn bị khá kỹ càng. Chỉ còn lại một công việc khá gay go là Hiếu không biết đi đường nào tới trường là nhanh nhất.

Thường ngày Hiếu không quan tâm tới vấn đề này lắm cho nên bây giờ Hiếu không biết phải làm sao cả. Bản đồ thành phố là gồm có $N$ nút giao thông và $M$ con đường nối các nút giao thông này. Có $2$ loại con đường là đường $1$ chiều và đường $2$ chiều. Độ dài của mỗi con đường là một số nguyên dương.

Nhà Hiếu ở nút giao thông $1$ còn trường ĐH BK ở nút giao thông $N$ . Vì một lộ trình đường đi từ nhà Hiếu tới trường có thể gặp nhiều yếu tố khác như là gặp nhiều đèn đỏ, đi qua công trường xây dựng, ...phải giảm tốc độ cho nên Hiếu muốn biết là có tất cả bao nhiêu lộ trình ngắn nhất đi từ nhà tới trường. Bạn hãy lập trình giúp Hiếu giải quyết bài toán khó này.

Input

Dòng thứ nhất ghi hai số nguyên $N$ và $M$ .

$M$ dòng tiếp theo, mỗi dòng ghi $4$ số nguyên dương $K$ , $U$ , $V$ , $L$ . Trong đó:

$K = 1$ có nghĩa là có đường đi một chiều từ $U$ đến $V$ với độ dài $L$ .

$K = 2$ có nghìa là có đường đi hai chiều giữa $U$ và $V$ với độ dài $L$ .

Output

Ghi hai số là độ dài đường đi ngắn nhấn và số lượng đường đi ngắn nhất. Biết rằng số lượng đường đi ngắn nhất không vượt quá phạm vì int64 trong pascal hay long long trong C++.

Sample Input

Copy

3 2
1 1 2 3
2 2 3 1

Sample Output

Copy

4 1

Note

Giới hạn: $1 \leq N \leq 5000$ $1 \leq M \leq 20000$ Độ dài các con đường $\leq 32000$

Bình luận

Hãy đọc nội quy trước khi bình luận.

-10

danghuyro đã bình luận 1:51:50 sa, 27/09/2023

bài này làm sao:)))???

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-10

PhamNhatVuong45 đã bình luận 3:05:16 sa, 18/06/2024

biet ong Liem ko ?

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-80

James2008 đã bình luận 1:54:19 sa, 27/09/2023

bài dễ vậy cx không biết làm nx, xóa acc vnoi đi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-66

James2008 đã bình luận 1:53:43 sa, 27/09/2023

ib anh chỉ cho e

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

daphne đã bình luận 2:37:21 sa, 18/09/2023

Số lượng đường đi ngắn nhất vượt quá phạm vi int64 trong pascal hay long long trong C++ mà nhỉ :(

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-7

PizzaPasta đã bình luận 8:49:45 sa, 24/01/2024

bignum

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-26

trongtenlinhcbhk64 đã bình luận 8:33:30 sa, 30/04/2023

tính số cách kiểu gì nhỉ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.