Cây khung dày nhất

Xem dạng PDF

Gửi bài giải

Điểm: 0,01
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.