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 (1 <= n <= 10000; 1 <= m <= 15000)

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í dụ: cạnh thứ 1 nối 2 đỉnh 1 và đỉnh 2 có trọng số là 3 thì ta nhập 1 2 3) và c trọng số của cạnh đó (1 <= u, v <= n; 0 <= c <= 10000).

Output

Gồm các cạnh của cây khung nhỏ nhất. Mỗi dòng chứa thông tin 1 cạnh (chỉ số đầu, chỉ số cuối, trọng số)