题目描述

可达星球上的人们非常喜欢串门聊天，并且如果自己可以和星球上的所有人都聊上天的话，那么他们就会认为自己生活的星球是快乐星球。但是可达星人非常讨厌走路，他们觉得路有多长他们就会减少多少快乐。现在已经知道某些可达星人之间的距离，请你确定可达星球是否是快乐星球，如果是，可达星人至少会减少多少快乐。

输入格式

第一行两个整数n，m，表示有n个可达星人，已知m个可达星人间的距离。 接下来m行每行三个整数a，b，d，表示可达星人a和可达星人b之间的距离为d。

输出格式

若可达星球是快乐星球，则输出一个整数，为可达星人减少的快乐的最小值。若可达星球不是快乐星球，输出“Not QwQ"。

样例输入

5 7
1 3 10
2 3 5
1 4 7
3 4 2
2 5 6
1 2 3
4 5 5

样例输出

15

数据范围与提示

对于30%的数据，$n \leq 20, m \leq 30$。

对于100%的数据， $n \leq 5000, m \leq100000$。