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

MST25 - Cây khung nhỏ nhất - MST

Cây bao trùm (tiếng Anh: spanning tree), còn được gọi là cây khung, của đồ thị G là cây con chứa tất cả các đỉnh của G. Nói cách khác, cây bao trùm của một đồ thị G là một đồ thị con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình.

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G

Input

Dòng 1: Chứa hai số n, m .

M dòng tiếp theo: Dòng thứ i có dạng ba số nguyên u, v, c. Trong đó u, v là chỉ số hai đỉnh đầu mút của cạnh thứ i và c trọng số của cạnh đó .

Output

Dòng 1: Ghi trọng số của cây khung nhỏ nhất

n-1 dòng tiếp theo: mỗi dòng ghi 2 số i, j mô tả 1 cạnh đã chọn.

Example

Input:
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2

Output:
5
2 1
3 1
4 2
5 2
6 3

Giới hạn:
1 <= n <= 100
1 <= m <= n(n-1)/2
1 <= c <= 10000

Được gửi lên bởi:special_one
Ngày:2009-01-04
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP JAVA PAS-FPC

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.