A. FIREG - Trạm cứu hỏa

Một mạng giao thông có nút đánh số từ đến , giữa một số cặp nút có đường đi hai chiều và mạng liên thông. Hiện nay toàn bộ hệ thống đường rất xấu.

Cần chọn một nút đặt trạm cứu hoả và một số đoạn đường để nâng cấp sao cho với hệ thống chỉ gồm những đoạn đường được nâng cấp, từ trạm cứu hoả đến mỗi nút có đúng một đường đi và khoảng cách từ nút xa trạm nhất đến trạm là nhỏ nhất có thể được.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương và là số nút giao thông và số tuyến đường hai chiều;
• dòng tiếp theo, mỗi dòng chứa ba số nguyên dương với ý nghĩa là có tuyến đường hai chiều nối hai nút với độ dài .

Dữ liệu ra:

• Dòng đầu ghi hai số nguyên dương là và cho biết nút được chọn làm trạm cứu hỏa và khoảng cách từ nút trạm đến nút xa nhất;
• Những dòng sau, mỗi dòng ghi hai số nguyên dương là hai đầu mút của một tuyến đường cần nâng cấp.

Đối với dữ liệu vào và dữ liệu ra: Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.

Ví dụ:

Dữ liệu vào:

5 8
1 2 50
1 3 30
1 4 100
1 5 10
2 3 5
2 4 20
3 4 50
4 5 10

Dữ liệu ra:

4 25
1 5
2 3
2 4
4 5

Giới hạn:

• .