A. Лорензо Вон Маттерхорн

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Барни Нью Йорк хотод амьдардаг. Нью Йорк хот хязгааргүй олон уулзвартай бөгөөд эдгээрийг 1-ээс эхлэн бүхэл эерэг тоогоор дугаарласан. Эерэг бүхэл $i$ болгоны хувьд, $i$ ба $2i$ уулзварууд болгоны хооронд болон $i$ ба $2i+1$ уулзвар болгоны хооронд зам байна. Эндээс та дурын 2 уулзварын хооронд хамгийн ойрхон бөгөөд онцгой траектор байна гэдгийг харж болно.

Анх бүх замаар үнэ төлбөргүй зорчдог байв. Гэхдээ удахгүй Слапсгивинг баяр болох гэж байгаа болохоор $q$ ширхэг арга хэмжээ болох гэж байна. Энд 2 төрлийн арга хэмжээ болно:

1. Засгийн газар шинэ дүрэм гаргах. Дүрмийг бүхэл тоонууд болох $v$, $u$, ба $w$-аар тэмдэглэдэг. Энэ дүрэм нь $u$-ээс $v$ уулзвар хүртэл хамгийн богино траекторийн зам болгоноор зорчиход төлбөр төлөх бөгөөд төлбөр нь $w$ доллараар ихсэх юм (жишээ нь: замын төлбөр $0$ байсан бол шинэ дүрэм гарсаны дараа $0+w$ төлбөртэй болно).

2. Барни найз охиноо тэврэхийг хүсч байгаа бөгөөд найз охин нь $u$ уулзвар дээр байгаа (тэрээр Лорензо Вон Маттерхорн гэх хуурамч нэрээ ашиглаж байгаа). Тиймээс Барни $v$ уулзвараас хөдөлж эхлэн $u$ уулзвар дээр очих ёстой. Тэрээр 2 уулзварын хооронд явахдаа үргэлж хамгийн богино траектороор явдаг (энэ нь хамгийн цөөн тооны зам эсвэл уулзвараар дайрдаг гэсэн үг).

Засгийн газарт таны тооцоолол хэрэг болжээ. Барни охинг тэврэх гэж явах болгонд та засгийн газарт түүнийг хэр их мөнгө төлөх ёстойг мэдээллэх шаардлагатай (түүний туулж буй замуудын нийт төлбөр).

Оролт

Эхний мөрөнд нэг бүхэл тоо $q$ ($1 ≤ q ≤ 1 000$) өгөгдөнө.

Дараагийн $q$ ширхэг мөрөнд цаг хугацааны дараалалтайгаар арга хэмжээ болгоны мэдээлэл өгөгдөнө. Хэрвээ засгийн газар дүрэм гаргах арга хэмжээ бол арга хэмжээ болгон $1$ $v$ $u$ $w$ хэлбэрээр өгөгдөнө. Харин Барнигийн $v$ уулзвараас $u$ уулзвар уруу очиж охин тэврэх гэ,ж байгаа бол энэ төрлийн арга хэмжээг $2$ $v$ $u$ хэлбэрээр өгнө.

Энд $1 ≤ v, u ≤ 10^{18}, v ≠ u, 1 ≤ w ≤ 10^{9}$ байна.

Гаралт

2 дахь төрлийн арга хэмжээ болгонд Барнигийн засгийн газарт төлөх ёстой төлбөрийг нэг мөрөнд хэвлэнэ үү. Хариултуудыг цаг хугацааны дараалалтайгаар хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
Гаралт
94
0
32

Тэмдэглэл

Жишээнд:

Уулзваруудын зураг:

  1. Траекторын уулзварууд: $3$, $1$, $2$, $4$.
  2. Траекторын уулзварууд: $4$, $2$, $1$.
  3. Траекторын уулзварууд: $3$, $6$.
  4. Траекторын уулзварууд: $4$, $2$, $1$, $3$. Зам болгоны төлбөр $32$, $32$, $30$. Тиймээс хариулт бол $32 + 32 + 30 = 94$.
  5. Траекторын уулзварууд: $6$, $3$, $1$.
  6. Траекторын уулзварууд: $3$, $7$. 2 уулзварын хоорондын төлбөр $0$.
  7. Траекторын уулзварууд: $2$, $4$. 2 уулзварын хоорондын төлбөр $32$ (Эхний арга хэмжээнээс болоод $30$-аар ихэссэн. 2 дахь арга хэмжээнээс болоод $2$-оор ихэссэн.).
Сэтгэгдлүүдийг ачааллаж байна...