大神

Time Limit: 3000MS

Memory Limit: 131072KB

Description

此题不是小坑坑系列,因此题目不是“小坑坑大神”。

Shangke7788是集训队的队长,因此他想认识更多的大神(也有大神想认识Shangke7788)。不过这是要付出时间和精力的。现在有N个大神(包括Shangke7788),他们都有自己想认识的人,因为各人的脾气不同,每个大神i对每个想要认识的大神j付出的代价不完全相同,记为c(i,j)。

同样作为大神的你,了解M个他们所有人的想法,请你安排一个方案,使得某一个大神可以直接或间接的认识到所有人(例如a想认识b,b想认识c,那么我们可以认为a也想认识c),并且总的代价和最小。

Input

输入有多组数据。每组数据第一行是一个整数N(N <= 100),M(M <= 10000)。

接下来M行,每行以格式s1, s2, c给出。

s1 大神A的名字(名字的长度不会超过20个字符)

s2 大神A想认识的牛人B的名字

c  认识的代价

Output

每组数据输出最小的代价,如果不存在这样的方案,输出“Poor Shangke7788”。

Sample Input

3 2
shangke7788 tsfn 1
tsfn watashi 2
3 1
bob alice 1

Sample Output

3
Poor Shangke7788

Hint

None

Source

alex4814

提交代码