说明

罗马大道，viae，是古罗马的重要基础建设，由公元前500年开始，并随罗马共和国及罗马帝国版国的扩大而延伸，这些罗马道路为罗马军队、官员及平民带来便捷的交通路径，更促进陆上通讯及贸易。这些道路由地方小路，连接上广阔、长距离的公路，连接各主要市镇及军事基地。罗马道路是主要由石头铺成，部分混入金属材料。道路由弧形的石头组成，这些石头形式和高于路面的行人道以方便排水，而道路两旁除有行人道外，还有马道和排水沟渠。罗马道路的建设有赖于精确的测量工序，包括透过切割山坡，用桥连接河流和沟壑，湿滑的地面部分用木桩作地基支撑。

作为帝国被器重的一员，元首屋大维死后，提比略决定授予你诺里库姆行省的长官职位，因为诺里库姆位于帝国的边疆，常年受到蛮族侵略，所以你上位的第一个任务就是要修缮被毁掉的路。因为修好路各个村庄的后勤补给才能跟上来。每修一米路就要五百塞斯太尔司，这可不是笔小数目，但是这时候财务长官刚刚被你不小心杀掉了，你只能亲自计算要修好路使得每个村庄都能来往最少所需要的费用。不过还好，你听说公元2021年4月25日的你能够使用高科技来很快的得出答案，你能帮帮过去的你吗？

输入格式

第1行输入2个数，n,m ( 1<=n<=120, 0<=m<=2000)     n表示有n个村庄，m表示有m条被毁掉的路。

接下来的m行，每行输入3个数u，v, w， 表示村庄u到村庄v有一条长w 的路。

(1<=w<=1e9)

村庄编号从1开始到n.

输出格式

输出一个数，表示最小所需要的塞斯太尔司。

如果不能试所有村庄相通，则输出“HuaiLiao.”

（注意行末有换行）

答案可能很大，请对其与 1e9+7 取模。

样例

2 1
1 2 3

1500

样例

3 3
1 2 1
1 3 4
2 3 1

1000

样例

3 1
1 2 1

HuaiLiao.

提示

假如1到2有路，2到3有路，那么1,3,2就可以互相往来。