刘老师的国外计划

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

刘老师有一个计划需要到 n 个城市中去,有 m 个航班从 u 城市飞往 v 城市需花费 w 元,并且此航班可往返,花费也是一样的。作为集训队的一员请你帮她规划一下在这n个城市的航班路线,使得两两城市之间的花费最小,求出任意一个城市到所有城市的最小花费。

Input

一组数据,输入 n (2 <= n <= 100000), m (1 <= m <= 500000)。

接下来有 m 行,每行输入 u (0 <= u < n), v (0 <= v < n), w (0 <= w <= 10^9),保证 u 与 v 不相同,且答案存在。

Output

输入前第一行先输出 ”Good Luck”,之后下一行输出一个整数代表答案,最后一行输出 ”QAQ”(均不包括引号)。

Sample Input

4 3
0 1 1
1 2 2
2 3 3

Sample Output

Good Luck
6
QAQ

Hint

Source

【2017年寒假集训 结训赛2】MLE_kenan