KZ菌的星际旅行

【题目描述】

Once upon a time.

   KZ菌十分的无聊，他打算去某星球上去玩，没错，地球已经满足不了KZ菌了。KZ菌现在在1号星球——也就是地球。

   KZ菌表示火箭实在太慢了，不过幸好科技早已发展到有星际旅行机器的存在，它们可以在近乎瞬间把KZ菌变成能量，然后送到远方，不过这些空间机器只能到达与之关联的另一台机器。当然，星际旅游局一定会去收KZ菌的钱的，因为他们还是需要赚钱什么的。不过还是有某些好心的企业，他们提供的有免费的空间机器。

   KZ菌作为一个并不富有的团子状外星人，自然不会自己去算如何才能更省钱，所以他把这个任务交给了他的助手——Illu酱，不过Illu酱作为一个高端的AI，她是相当不愿意做这么简单的问题，于是她把问题挂在了过去的网上。

【输入格式】

输入共有M+1行：

第1行有2个数 N M：

   表示KZ菌想去的星球编号N和现在已经被制造出M对星际旅行机器。

第2->M+1行中各有3个数a b s：

   表示某对空间机器被放在了编号为a和b的星球上，用这对空间机器星际旅游局会收KZ菌s元RMB。

【输出格式】

输出共有1行：

第1行有1个数：

   表示KZ菌来回要花的RMB。

【样例输入】

2 1
1 2 0

【样例输出】

0

【提示】

不会有人用负数、零、小数、无理数或虚数来为星球编号。

有关部门并没有发现第10,000,001号星球。

有关部门不会倒贴钱。

没有10,000,000以上对空间机器。

KZ菌没有2147483647RMB，但他一定可以到达他想去的星球。

表示KZ菌没有自己造空间机器的能力。

表示Illu酱可以变成电磁波来移动，所以不需要用空间机器。

第一个测试点一定是样例

PS：你的代码再好KZ菌也不会带你一起去的。

PPS：向KZNS@foxmail.com反馈。

【来源】

KZ's UBWH.