Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBSCHOOL - Đến trường

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbschool


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++.

Example

Input:
3 2
1 1 2 3
2 2 3 1

Output:
4 1

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

Được gửi lên bởi:special_one
Ngày:2008-10-11
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Nguyễn Minh Hiếu

hide comments
2014-08-09 15:40:14 Nắng
mất 3 tháng mới AC bài này :(
2014-08-04 09:38:31 ■■‡[ND] Bee Sociu■■‡
Chang co nhe~ :! Dijkstra thuong khong lam an duoc gi :v Phai Heap thoi
2014-08-02 12:40:07 Ðỗ Tuấn Kiệt
dijkstra heap nha anh emv :))
2014-07-01 06:03:40 ­
cho text ps ơi
2014-06-02 11:21:36 Kraken
time chặt quá! dijktra tối ưu đủ kiểu mà không được@@!

Last edit: 2014-06-02 11:21:59
2014-04-18 18:02:56 Thcs Ðặng Chánh Kỷ
Giảm time thành công vãi mất ac vì để mảng adj quá bé
2014-04-18 16:52:16 Thcs Ðặng Chánh Kỷ
ac được bài này sướng cả người mất hơn 3 ngày
2014-04-16 16:37:46 Thcs Ðặng Chánh Kỷ
kết quả sai sai ở đâu hầy
2013-11-26 16:01:47 Nguyễn Hoàng Nam
duyệt trâu cũng ac o(n^2) cẩn thận là ok ngay
2013-11-26 11:37:13 Xiao Lang
1 đấm AC

Last edit: 2013-12-18 15:29:30
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.