1-ден $n$-ге дейін нөмірленген $n$ қала бар. Сондай-ақ осы қалаларды байланыстыратын $n - 1$ екі бағытты жол бар, сондықтан кез келген екі $x$ және $y$ қаласы үшін $x$-тен $y$-ке баратын жол табылады. $i$-ші жол $u_i$ мен $v_i$ қалаларын қосады және оның құны $c_i$-ге тең. $i$-ші жолмен өткен сайын сіз $c_i$ тиын жұмсайсыз.
Сіз қазір 1-қаладасыз және барлық қалаларды аралап шығу үшін саяхаттағыңыз келеді. Әр секунд сайын, егер сіз $x$ қаласында болсаңыз, $x$ қаласымен жол арқылы тікелей байланысқан $y$ қаласын таңдап, $y$ қаласына өтіп, тиісті жолдың құнын төлей аласыз. Әрбір жолмен ең көбі екі рет өтуге болады. Барлық қалаларды аралап шығып, 1-қалада тұрған кезде саяхатыңызды аяқтай аласыз. Саяхаттың құны — сіз жасаған барлық жүрістердің жалпы құны.
Сондай-ақ бүтін $k$ саны берілген. Саяхат барысында сіз тегін купонды бір рет қолдана аласыз, ол сіздің келесі $k$ жүрісіңізді тегін етеді.
0-ден $2n - 2$-ге дейінгі әрбір $k$ үшін барлық қалаларды аралап шығатын және купонды тиімді пайдаланатын саяхаттың ең аз құнын есептеуіңіз керек.
Кіріс деректер
Бірінші жолда тест жағдайларының санын білдіретін бір бүтін $t$ ($1 \le t \le 400$) саны берілген. Әрбір тест жағдайы үшін:
Бірінші жолда қалалар санын білдіретін бүтін $n$ ($1 \le n \le 2000$) саны берілген.
Келесі $n - 1$ жол жолдарды сипаттайды. Осы жолдардың $i$-шісінде $i$-ші жол қосатын қалаларды және сол жолдың құнын білдіретін үш бүтін сан $u_i$, $v_i$ және $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$) берілген.
Кез келген екі қаланың арасында жол бар. $n$ мәндерінің қосындысы $2000$-нан аспайды.
Шығыс деректер
Әрбір тест жағдайы үшін $2n - 1$ бүтін саннан тұратын бір жолды шығарыңыз: 0-ден $2n - 2$-ге дейінгі $k$ мәндеріне арналған жауаптар.
Мысал
Кіріс деректер
2 5 1 2 2 2 3 3 2 4 1 4 5 3 7 1 2 1 1 3 1 1 4 4 3 5 5 3 6 1 6 7 4
Шығыс деректер
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Ескертпе
Бірінші тест жағдайында біз әрқашан $1, 2, 3, 2, 4, 5, 4, 2, 1$ маршрутымен саяхаттай аламыз, оның құндар тізбегі $2, 3, 3, 1, 3, 3, 1, 2$. Әрбір $k$ үшін тегін кесінділер төменде көрсетілген.
| $k$ | тегін кесінді | жауап |
|---|---|---|
| 0 | $[]$ | 18 |
| 1 | $[3]$ | 15 |
| 2 | $[3, 3]$ | 12 |
| 3 | $[2, 3, 3]$ | 10 |
| 4 | $[3, 3, 1, 3]$ | 8 |
| 5 | $[3, 3, 1, 3, 3]$ | 5 |
| 6 | $[2, 3, 3, 1, 3, 3]$ | 3 |
| 7 | $[2, 3, 3, 1, 3, 3, 1]$ | 2 |
| 8 | $[2, 3, 3, 1, 3, 3, 1, 2]$ | 0 |