Câu 2. Đường đến trường (7 điểm).
Ngày 20/9/2022 Sở GD&ĐT Quảng Bình tổ chức kỳ thi chọn đội tuyển chính thức dự thi học sinh giỏi Quốc gia tại điểm thi trường THPT Chuyên Võ Nguyên Giáp. Tất cả các bạn đã chuẩn bị khá kỹ càng. Chỉ có điều, các thí sinh dự thi rất lo lắng cho Nam vì nhà Nam cách điểm thi khá xa và bạn ấy không xác định được đi đường nào đến điểm thi là nhanh nhất. Thường ngày mọi người không quan tâm đến điều này, nhưng hôm nay là kỳ thi rất quan trọng nên không muốn bạn Nam đến trễ.     
Bản đồ thành phố Đồng Hới 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à Nam ở nút giao thông 1, điểm thi Trường THPT Chuyên Võ Nguyên Giáp ở nút giao thông N. Vì một lộ trình đường đi từ nhà Nam tới điểm thi 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 Nam muốn biết là có tất cả bao nhiêu đường đi ngắn nhất đi từ nhà tới điểm thi. Các bạn thí sinh hãy lập trình giúp Nam giải quyết bài toán này.
Dữ liệu vào: Cho trong file văn bản có tên SCHOOL.INP có cấu trúc:
   Dòng 1: Chứa hai số nguyên N và M (1 ≤ N ≤ 5000; 1 ≤ M ≤ 20000).
   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.
(1 ≤ U,V ≤  N; L ≤ 32000)
(Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách)
Dữ liệu ra: Ghi vào file văn bản có tên SCHOOL.OUT với cấu trúc:
   Dòng 1: Ghi 1 số là độ dài đường đi ngắn nhất.
   Dòng 2: Ghi 1 số là 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 vi int64 trong pascal hay long long trong C++.
Ví dụ:
SCHOOL.INP  
3   2 
1   1   2   3
2   2   3   1
SCHOOL.OUT
4
1