Дзи мод тарих дуртай ба модны асуудлуудыг шийдэх нь түүнд гайхалтай байдаг.

Дзид $n$ зангилаанууд ($1$-с $n$ хүртэл дугаарлагдсан) агуулсан жинтэй мод (чиглэлгүй, циклгүй холбоост граф) байна. $x$ ба $y$ зангилаануудын хоорондох хамгийн богино замын хамгийн урт ирмэгийг $g(x, y)$ $(1 ≤ x, y ≤ n)$ функцээр тодорхойлно. Ялангуяа бүх $z$-н хувьд $g(z, z) = 0$ байна.

$p_{1}, p_{2}, ..., p_{n}$ $(1 ≤ p_{i} ≤ n)$ дарааллын бүх бүхэл тоонуудын хувьд нь $f(p)$ функцыг тодорхойлно .

Дзи ийм $p$ дарааллын $f(p)$-д байгаа хамгийн их боломжит утгыг олохыг хүсэж байна. Гэхдээ нэг хязгаарлалт байгаа: $j$ элемент $p$ дараалалд хамгийн ихдээ $x_{j}$ удаа гарч ирж чадна.

Тодорхойлсон хязгаарлалтын хүрээнд байж болох хамгийн их $f(p)$-г олно уу.

Оролт

Эхний мөр нь $n (1 ≤ n ≤ 3000)$ бүхэл тоог агуулна.

Дараагийн $n - 1$ мөр бүр нь $a_{i}, b_{i}, c_{i} (1 ≤ a_{i}, b_{i} ≤ n; 1 ≤ c_{i} ≤ 10000)$ гурван бүхэл тоог агуулах ба $a_{i}$ ба $b_{i}$-н хоорондох $c_{i}$ урттай ирмэгийг илэрхийлнэ. Эдгээр ирмэгүүд нь модны ирмэгүүд гэдэг нь баталгаатай.

Дараагийн $n$ мөр бүр нь $x$ дарааллын элементүүдийг тодорхойлно. $j$-р мөр нь $x_{j} (1 ≤ x_{j} ≤ n)$ бүхэл тоог агуулна.

Гаралт

Хариуг илэрхийлсэн нэг бүхэл тоо хэвлэнэ.

In the first sample, one of the optimal $p$ is $[4, 3, 2, 1]$.