小苯正在配置机房的网络环境。 具体来说，机房有 台主机（电脑），和 条网线，每条网线都有严格的连接规定，具体的：第 条网线必须连接 和 这两台主机，连接后使用该网线传输数据的花费为 。 熟练电脑的小苯很快就配好了所有的线路，此时无聊的小苯突然对这个网络的最小传输花费产生了兴趣，他想知道从 号主机传输数据到 号主机的最小花费。但很快他就求出了这个答案，因此他认为这个问题太简单了，他现在提出了一个更难的问题： 对于 到 的每一条网线，是否存在某个从 号主机到 号主机的最小花费传输路径一定经过了这条网线。 他被自己提出的新问题难住了，请你帮帮他吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：在第一行输入两个正整数 ，分别表示机房中的主机个数 和网线条数 。在紧接着的 行中，每行三个正整数 ，分别表示每条网线连接的两个主机的编号，以及在此网线传输数据消耗的代价。（保证同一个测试文件中， 的总和不超过 ， 的总和不超过 。）

输出描述:

对于每组测试数据，在单独的一行上输出一个长度为  的  串 。（如果第 条网线一定处于某个从  号主机到  号主机的最小花费传输路径上，则  "1"，否则  "0"）。

备注:

Python同学建议选择通过Pypy、Pypy3语言来进行提交。