Cho một đồ thị vô hướng có ~n~ đỉnh và ~m~ cạnh có trọng số.
Ta định nghĩa giá trị của một cây khung là hiệu trọng số của cạnh có trọng số lớn nhất với cạnh có trọng số bé nhất.
Yêu cầu: Tìm giá trị bé nhất của một cây khung được tạo ra từ đồ thị đã cho.
Nhắc lại kiến thức, một cây khung là một đồ thị liên thông có ~n~ đỉnh và ~n-1~ cạnh có trọng số.
Input
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ (~2 \leq n \leq 1000~, ~0 \leq m \leq 10000~) — là số đỉnh và số cạnh của đồ thị.
Trong ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên ~u_i~, ~v_i~ và ~w_i~ (~1 \leq u_i, v_i \leq n~, ~|w_i| \leq 10^9~) — là cạnh nối giữa hai đỉnh ~u_i~ với ~v_i~ và có trọng số là ~w_i~.
Output
Gồm một dòng duy nhất là đáp án của yêu cầu đề bài; nếu không tìm được thì hãy in ra "NOT FOUND".
Sample Input 1
3 3
1 2 2
2 3 1
1 3 2
Sample Output 1
0
Sample Input 2
3 1
1 2 2
Sample Output 2
NOT FOUND
Bình luận