Tree
یک درخت $n$ راسی به شما داده شده است. روی هر یک از یالهای درخت عددی بین $1$ و $n-1$ نوشته شده و همه این اعداد متمایز هستند. به مسیر بین دو راس $i$ و $j$ مناسب میگوییم اگر
شما باید برنامهای بنویسید که با دریافت اطلاعات درخت تعداد میسرهای مناسب آن را پیدا کند.
ورودی
در سطر اول ورودی، عدد $n$، تعداد رئوس درخت قرار دارد.
در $n-1$ سطر بعدی در هر سطر به ترتیب سه عدد $u$ ، $v$ و $c$ آمده است که نشان میدهد یک یال بین دو راس $u$ و $v$ درخت قرار دارد که عدد نوشته شده روی آن $c$ است.
همهی اعداد نوشته شده روی یالهای درخت متفاوت و بین $1$ و $n-1$ هستند. همچنین ورودی یک درخت را توصیف میکند.
$1 \le n \le 100000$
در حداقل $40$ درصد تستها $n$ از $3000$ بیشتر نیست.
خروجی
در تنها سطر خروجی پاسخ سوال را چاپ نمایید.
محدودیتها
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
4
1 2 3
1 3 2
2 4 1 | 4 |
توضیحات
در مثال نمونه مسیرهای بین رئوس $(1,2)$ ، $(1,3)$ ، $(2,3)$ و $(2,4)$ مناسب هستند.