小苯的网络配置

题号：NC285807
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯正在配置机房的网络环境。
具体来说，机房有 $n$ 台主机（电脑），和 $m$ 条网线，每条网线都有严格的连接规定，具体的：第 $i$ 条网线必须连接 $u_i$ 和 $v_i$ 这两台主机，连接后使用该网线传输数据的花费为 $w_i$ 。

熟练电脑的小苯很快就配好了所有的线路，此时无聊的小苯突然对这个网络的最小传输花费产生了兴趣，他想知道从 $1$ 号主机传输数据到 $n$ 号主机的最小花费。但很快他就求出了这个答案，因此他认为这个问题太简单了，他现在提出了一个更难的问题：

对于 $1$ 到 $m$ 的每一条网线，是否存在某个从 $1$ 号主机到 $n$ 号主机的最小花费传输路径一定经过了这条网线。

他被自己提出的新问题难住了，请你帮帮他吧。

输入描述:

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

输出描述:

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

示例1

输入

复制

输出

复制

101010
00

说明


对于第一组测试数据：
如图，圈成红色的网线都是符合要求的网线，即：从一定存在某个从  号主机传输到  号主机的最短花费传输路径经过此网线。

第二组测试数据中，由于  号和  号主机之间无法传输数据，因此所有的网线都不符合要求。

备注:

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