U330814 七夕

> 伫倚危楼风细细，望极春愁，黯黯生天际。草色烟光残照里，无言谁会凭阑意。\ > 拟把疏狂图一醉，对酒当歌，强乐还无味。衣带渐宽终不悔，为伊消得人憔悴。\ > —— 柳永《蝶恋花》 今天是癸卯年**七夕**。 小 P 开始了今年的“吃瓜行动”。

**前排提示：题目中含有虚构成分，请勿当真。** 小 P 的班级为了庆祝七夕节（~~某些 CP 约会~~），决定全班共 $m$ 人一起去看电影。 假设暑假期间，同学们都在家，各自写各自的作业。小 P 需要拜访班里每一位同学，并送上邀请函。 可是，小 P 只知道 $n$ 个同学家的位置，且每个同学只知道其他 $n$ 个同学家的住址，被知道住址的同学也知道该同学的住址。 也就是说，全班同学之间存在一个**有权无向图**。 小 P 前往某个同学的家，需要花费一定的时间。但**拜访不计入时间总花费**。 现在给出每个同学知道的位置和前往的时间，求小 P 要全部拜访完所需的**最少**时间。 若无法拜访到所有同学，输出 `Oh no!`。

第一行输入两个整数 $n$、$m$。 对于接下来 $(mn-m)$ 行，每行输入： - 两个字符串 $S_1$，$S_2$：**有一条边联通 $S_1$ 和 $S_2$**，即名为 $S_1$ 的同学知道名为 $S_2$ 的同学的住址。**保证有且仅有一条路径可以联通 $S_1$，$S_2$**。 - 一个整数：**表示从 $S_1$ 到 $S_2$ 的花费**，即小 P 前往所需的时间。

输出一个整数，小 P 拜访所有同学所需的最短时间。

对于所有数据，$1\le n\le m\le100$。