Đề bài

Mạng lưới giao thông trong thành phố có ~ n ~ điểm, được đánh số từ ~ 1 ~ tới ~ n ~. Giữa hai điểm giao thông trong thành phố có thể có đường đi hoặc không có đường đi. Nếu có đường đi từ ~ u ~ đến ~ v ~ thì cũng có đường đi từ ~ v ~ đến ~ u ~. Đường đi giữa hai điểm ~ u, v ~ có thể là đường bộ hoặc đường sông. Tuy nhiên, việc di chuyển bằng đường sông rất vất vả, nên người dân trong thành phố rất ít khi lựa chọn.

Yêu cầu: Hãy giúp người dân trong thành phố tìm đường đi ngắn nhất từ điểm giao thông ~ 1 ~ đến điểm giao thông ~ n ~ sao cho số lần phải di chuyển bằng đường sông là ít nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~ n ~ và ~ k ~, với ~ k ~ là số đường sông trong thành phố (~ n < 10000, k < 50 ~).
• ~ k ~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~ x, y ~, tương ứng với các đường sông trong thành phố.
• Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~ a, b, c ~, tương ứng là đường bộ đi từ ~ a ~ đến ~ b ~ có độ dài là ~ c ~ (~ c < 1000 ~).

Output

• Ghi ra 2 dòng:
  • Dòng đầu tiên: tổng độ dài đường bộ ngắn nhất đi từ điểm giao thông ~ 1 ~ đến điểm giao thông ~ n ~.
  • Dòng thứ hai: số lần ít nhất phải di chuyển bằng đường sông trên đường đi đó.
• Nếu không có đường đi từ điểm ~ 1 ~ đến điểm ~ n ~, ghi ra -1.

Ví dụ

Input

7 3
1 2
5 6
3 4
1 4 5
1 3 2
4 5 3
2 3 9
6 7 8

Output

16
1

Giải thích:

• Đường đi từ 1 đến 7 ngắn nhất thỏa mãn yêu cầu là: ~ 1 \to 4 \to 5 \to 6 \to 7 ~.
• Tổng chi phí đường bộ: ~ 5 + 3 + 8 = 16 ~.
• Chỉ phải sử dụng đường sông ~ 1 \to 2 ~, số lần đi đường sông là ~ 1 ~.