Энэ улсад $1$-c $n$ хүртэл эерэг бүхэл тоон утгаар дугаарлагдсан яг $n$ хот бий. Хот бүрт энэ хотод байрласан нисэх буудал байдаг.

Мөн энд $m$ нислэг хийдэг ганцхан нисэх компани бий. Харамсалтай нь эдгээр нислэгийг ашиглахын тулд та энэ компаны байнгын үйлчлүүлэгч байх ёстой ба өөрөөр хэлбэл та $a_{i}$ хотоос $b_{i}$ хот хүрэх $i$ нислэгийн өмнө хамгийн багадаа $d_{i}$ нислэг хийчихсэн байх ёстой ба ингэж байж энэ нислэгт багтах боломжтой.

$i$ нислэг нь яг $a_{i}$ хотоос $b_{i}$ хотруу ниснэ. Энэ нь $b_{i}$ хотоос $a_{i}$ хотруу нисэхэд ашиглагдаж чадахгүй. Нэг сонирхолтой зүйл бол нэг хотоос гарч уг хотдоо ирдэг тэнгэрийн үзэсгэлэнт хэсгээр явах зугаа цэнгэлийн нислэгүүд байж болно.

Та $1$-р хотоос $n$-р хотод хүрэх хэрэгтэй. Харамсалтай нь та өмнө нь онгоцоор аялаж байгаагүй. Та $n$ хотод хүрэхийн тулд хамгийн багадаа хэдэн нислэг үйлдэх вэ?

Нэг нислэг хэд хэдэн удаа ашиглагдаж болно.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 150$, $1 ≤ m ≤ 150$) байх ба тус улсын хотуудын тоо болон компаний үйлчилдэг нислэгүүдийн тоо.

Дараагийн $m$ мөрөнд $a_{i}$, $b_{i}$, $d_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $0 ≤ d_{i} ≤ 10^{9}$) тоонуудыг агуулах ба $a_{i}$ хотоос $b_{i}$ хот хүрэх дугаартай нислэгийг илэрхийлэх ба зөвхөн хамгийн багадаа $d_{i}$ нислэг хийсэн байх үйлчлүүлэгчдэд нээлттэй.

Гаралт

Хэрвээ агаарын замыг ашиглан $1$ дугаартай хотоос $n$ дугаартай хот хүрэх боломжгүй бол "$Impossible$" (хашилтгүйгээр) гэж хэвлэ.

Гэхдээ ядаж нэг зам байвал та эцсийн цэгт очиход хийх шаардлагатай нислэгүүдийн хамгийн бага тоог илэрхийлэх бүхэл тоон утгыг хэвлэ.