Bách thách đố Dương và Thanh chơi một trò chơi. Có một đất nước gồm ~n~ thành phố, các thành phố được đánh số từ ~0~ đến ~n - 1~. Các thành phố được nối với nhau bằng ~m~ con đường 2 chiều. Những con đường này sẽ nối giữa 2 thành phố khác nhau và giữa 2 thành phố có thể có nhiều con đường khác nhau.

Hiện tại đất nước đang diễn ra cuộc chiến giữa đội quân A và đội quân B. Mỗi đội quân có thể di chuyển dọc theo các con đường để đi từ thành phố này sang thành phố khác. Đất nước muốn ngăn chặn chiến tranh diễn ra bằng cách phá hủy một vài con đường sao cho hai đội quân này không thể gặp được nhau và người chơi muốn giảm thiểu tối đa kinh phí để làm việc đó. Hai đội quân có thể gặp nhau khi tồn tại một con đường chưa bị phá hủy giữa 2 thành phố mà 2 đội quân này đang chiếm đóng.

Người chơi sẽ phải chọn 2 thành phố khác nhau cho 2 đội quân này chiếm đóng và số điểm của người chơi là kinh phí ít nhất để đất nước ngăn chặn chiến tranh. Cả 2 bạn đều muốn số điểm của mình càng thấp càng tốt. Dương là một con người rất thông minh nên cậu dễ dàng tìm được cách chọn 2 thành phố tối ưu nhất. Tuy nhiên Thanh không hiểu về game nên đã chọn ngẫu nhiên 2 thành phố bất kì trong ~n~ thành phố để làm đáp án.

Sau cùng, Bách muốn biết số điểm của Dương và trung bình số điểm của Thanh sẽ là bao nhiêu?

Yêu cầu: Nếu ~T = 1~ in ra số điểm của Dương. Nếu ~T = 2~ in ra số điểm trung bình của Thanh nhân với ~n \times (n - 1)~. Đảm bảo đáp án cần in ra luôn là số nguyên.

Input

• Dòng đầu tiên ghi 3 số ~T, n, m~ (~1 \le T \le 2~).
• Mỗi dòng trong ~m~ dòng tiếp theo ghi 3 số ~u_i, v_i, w_i~ (~0 \le u_i, v_i < n, 1 \le w_i \le 10^6~) chỉ một con đường nối 2 thành phố ~u_i~ và ~v_i~ và cần ~w_i~ đồng tiền để phá hủy con đường đó.

Output

• In ra kết quả theo yêu cầu của đề bài.