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

VOSTRIP - VOSTRIP

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vostrip


Sau khi C11 chính thức mang tên mới là VOS - VNOI ONLINE SERIES, các admin VOS của chúng ta quyết định ăn mừng bằng cách tổ chức đi du lịch ở... vương quốc dừa của pirakute. Lại nói về vương quốc dừa của pirakute, cả vương quốc bao gồm N hòn đảo được nói với nhau bởi N-1 cây cầu dừa, sao cho từ bất kì hòn đảo nào cũng tồn tại duy nhất một đường đi đến các hòn đảo khác. 

 Đoàn du lịch các admin của chúng ta đã tham gia rất nhiều tour tham quan trên vương quốc dừa, mỗi tour bao gồm việc xuất phát từ một hòn đảo u, qua một dãy các hòn đảo bằng các cây cầu dừa sao cho mỗi hòn đảo chỉ đi qua một lần duy nhất, và kết thúc ở hòn đảo v.

 Sau chuyến du lịch dài ngày, cả đoàn của chúng ta đã vui chơi thỏa thích, có điều do mãi vui chơi nên chả ai nhớ được tổng cộng đoàn đã tham gia tất cả bao nhiêu tour du lịch. Rất may là mỗi cây cầu dừa ở vương quốc dừa đều có gắng máy ghi hình để đếm số lần đoàn chúng ta đi qua cây cầu dừa đó. Nghĩa là mỗi lần đoàn tham quan tham gia 1 tour tham quan từ đảo u đến đảo v thì các cây cầu dừa trên đường đi từ đảo u đến đảo v sẽ đếm thêm 1 lần đoàn đi qua. Dựa vào số liệu hệ thống các hòn đảo, các cây cầu dừa và số lần đoàn du lịch đã đi qua các cây cầu đó, hãy đếm số lượng tour du lịch ít nhất mà đoàn tham quan đã tham gia.

 

Ví dụ, ta có sơ đồ vương quốc dừa như bên dưới với 6 hòn đảo. Trong đó đoàn tham quan đã đi qua cây cầu dừa 3-4 được 2 lần, đi qua các cây cầu dừa 1-2, 4-5, 4-6 được 1 lần, và chưa đi qua cây cầu dừa 2-3 lần nào. Trong trường hợp này, đoàn tham quan của chúng ta phải tham gia ít nhất là 3 tour tham quan:

  • Tour thứ 1: 1 - 2
  • Tour thứ 2: 3 - 4 - 5
  • Tour thứ 3: 3 - 4 - 6

VOSTRIP

Input

  • Dòng đầu tiên có số N là số hòn đảo.
  • N-1 dòng tiếp theo, mỗi dòng chứa 3 số u, v, w cách nhau bởi 1 dấu cách, có nghĩa là có 1 cây cầu dừa nối hòn đảo u, v và đoàn tham quan đã đi qua cây cầu dừa đó tổng cộng w lần.

Output

  • Một số duy nhất là số lượng tour tham quan ít nhất mà đoàn của chúng ta đã tham gia.

Giới hạn:

  • Trong 20% số test có n <= 10, 0 <= w <= 5
  • Trong 20% số test kết tiếp có n <= 100, 0 <= w <= 100
  • Trong 20% số test kế tiếp có n <= 10000, 0 <= w <= 10000
  • Trong 40% số test còn lại có n <= 106, 0 <= w <= 1012

Example

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

Output:
3

Được gửi lên bởi:Hacker7
Ngày:2013-12-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

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