Програмчлалын олимпиадын бодлогын архив

Мэдээллийн нууцлалын албаны дарга Д өөрийн сүлжээний бүтцийг сайжруулж сүлжээний шинэ технологийг нэвтрүүлжээ. Шинэ технологиор бүтээсэн сүлжээний бүтэц нь дараах бүтэцтэй:

Сүлжээний төхөөрөмжүүд нь өөртэйгөө холбогдохгүй байх ба бүгд хоорондоо холбоотой. Төхөөрөмжүүд нь хоорондоо нэг л шугамаар холбогдох бөгөөд энэ шугамаар мэдээлэл хоёр тийшээ урсах байдлаар дамждаг, Мөн мэдээллийн урсгал бүрийг түгжих электрон түгжээ байрлуулжээ. Электрон түгжээ бүрийн түлхүүрийн нууцлал нь X-64 нууцлалын системээр хангагдсан, Дээрх нууцлалын системээр түгжигдсэн түлхүүрийн зарчимыг хакер Б хэд хэдэн довтолгоо хийж нээж илрүүлж чаджээ. Түүний нууцлалын зарчим нь маш төвөгтэй байсан тул хакер Б нейроны сүлжээг ашигласан програмаар нээн илрүүлэх боломжтой болсон байна.

Нууцласан түлхүүр нь ямар нэг K(1<=K<=11) тэмдэгтээс тогтох үг байх ба уг түлхүүрийг тайлах хугацаа нь нууцласан түлхүүрийн уртаар тодорхойлогдоно. Нэг тэмдэгтийг тайлахад програм 1 секунд зарцуулна.

Одоо хакер Б мэдээллийн урсгалыг нь бүгдийг нь нээсэн үед нь зарим түлхүүрийг хааж тухайн байгууллагын мэдээллийн урсгалын бүрэн бүтэн чанарыг байнга алдагдуулах төлөвлөгөөгөө хэрэгжүүлэхийн тулд  бүх түлхүүрүүдийг тайлах шаардлага тулгарчээ. Гэтэл зарим электрон түгжээг хаах үед сүлжээний бүтцээс нь болоод тухайн байгууллагын мэдээллийн урсгал хаагдахгүй харин ч хурдан ажиллах болжээ. Тайлсан түлхүүрээрээ электрон түгжээг хаахад мэдээллийн урсгал хаагдахгүй байгаа тул тэр мэдээллийн урсгал нь бүрэн нээгдсэн байх үед нэг электрон түгжээг хаахад л мэдээллийн урсгалын бүрэн бүтэн байдал алдагдаж байхаар ялгаатай тэдгээр бүх түгжээнүүдийн түлхүүрийг тайлахад нийт хичнээн хугацаа зарцуулахыг мэдэх шаардлагатай болжээ.

Тэгвэл сүлжээний бүтэц мэдэгдэж байгаа үед мэдээллийн урсгалыг бүгдийг нь нээлттэй байх үед түгжихэд бүрэн бүтэн байдал нь алдагдаж байх түгжээнүүдийн түлхүүрийг олж нээхэд нийт хугацааг олох програм зохионо уу.

Тайлбар: Мэдээллийн урсгалын бүрэн бүтэн байна гэдэг нь аль ч төхөөрөмж нь дурын нэг төхөөрөмжтэй мэдээлэл солилцох боломжтой байна гэсэн үг.

Input

Оролтын эхний мөрөнд М (1<=M<=100000) сүлжээний төхөөрөмжийн тоо ба N (1<=N<=2000000) мэдээллийн урсгалын тоо нэг хоосон зайтайгаар тусгаарлагдан байрлана. Дараагийн N мөр тус бүрд  a, b (1<=a, b<=M) оройн дугаарууд, мөн мэдээллийн урсгал дээр байрлах түгжээний нууцлагдсан түлхүүр болох нэг үг хоорондоо нэг хоосон зайгаар тусгаарлагдан байрлана. Тухайн үг англи цагаан толгойн жижиг үсгүүдээс тогтоно.

Output

Гаралтанд мэдээллийн урсгалыг бүгдийг нь нээлттэй байх үед нь түгжихэд бүрэн бүтэн байдал нь алдагдаж байх түгжээнүүдийн түлхүүрийг олж нээх нийт хугацааг байна. Хэрэв мэдээллийн бүрэн бүтэн байдал алдагдахгүй байвал 0-ийг хэвлэ.

Example

Input:
4 3 
1 2 bbb
2 3 ccc
3 4 ddd
Output:
9

Input:

4 3 
1 2 bbb
2 3 ccc
3 4 ddd

Output:

9