[Login|Register]
Problems

Status

Rank

Problem 1354
WHZ和她的妹子们
Time Limit: 3000ms
Memory Limit: 65536kb
Description
WHZ最近在USTC的生活实在太过无聊,于是他通过手机摇微信认识了四只妹子(中科大东、西区,安大,安医附院各一只)。他和四只妹子在网上一见如故,并且顺利的拿到了四只妹子的宿舍地址。现在他要MYT帮他计算一下去找哪只妹子需要花费的时间最少。MYT表示这个问题简直弱爆了,而且她对WHZ去找妹子这种事儿表示很反感很不屑,所以她把这个工作交给了你。
为了使得问题变得更加简明,现将问题抽象如下:设给你一个无向图,顶点分别标号1..n,其中有m条路连接着n个顶点。WHZ位于1号顶点,四只妹子分别位于a、b、c、d四个点,由于WHZ找到妹子的心情实在太过迫切,他可以选择一条路来仅使用这条路花费的三分之一(下取整)的时间通过这条路(最多仅能对一条路这么做!)问题是:他能花费最少的时间找到的妹子是哪只?
Input
输入数据包含多组数据,不多于10组。
对每组数据:
第1行包括两个数n、m,分别是图中顶点的个数和边的条数
第2行到第m+1行每行有三个数x,y,v,代表从x到y存在一条路,走过这条路花费时间为v。
第m+2行包括四个数a,b,c,d,第i个数代表第i只妹子所在的顶点。

数据范围:n<=100,m<=10000,数据保证无重边
Output
对每组数据输出一行,为了足够有代表性,我们输出这个妹子最喜欢对WHZ说的一句话。(均不包含双引号)
妹子1:"Hehe"
妹子2:"Quxizao"
妹子3:"Qushuijiao"
妹子4:"Quchidongxi"
如果WHZ到两只妹子所在位置花费的时间相等或者他找不到任何一只妹子,那么他就会很不爽,输出"Shuiwujiaoqu"。
Sample Input
100 0
2 1 3 4

4 4
1 2 10
2 4 10
1 3 1
3 4 100
1 2 3 4

5 4
1 2 10
2 4 10
1 3 1
3 4 100
5 2 3 4

100 0
1 1 1 1
Sample Output
Quxizao
Shuiwujiaoqu
Qushuijiao
Shuiwujiaoqu
Source
wyh@USTC ACM team
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).