物理课上，nodgd一拍脑袋，发明了一个最短路算法：给无向图的每个节点制作一个小球，每条边制作一根绳子，绳子的长度就是边的权值；将最短路问题的起点对应的小球缓缓提起，然后测量每个小球到起点小球的距离，就得到了起点到每个节点的最短路。nodgd发现这个算法非常厉害——它的时间复杂度为$O(1)$。

nodgd打算在课上给大家演示这个最短路算法，于是用数据生成器生成了一组数据，即一个$n$个节点$m$条边的无向图。nodgd发现，分别选取不同的最短路起点，有些绳子总是处于松弛状态，有些绳子总是处于绷紧状态，剩下的绳子时而绷紧时而松弛，这样可以将绳子分成三类。现在nodgd想知道，每种绳子属于哪一类？

1第一行两个整数$n,m$，表示无向图的节点数和边数。

接下来$m$行，每行三个整数$a_i,b_i,c_i$，表示第$i$条无向边连接$a_i,b_i$节点，权值为$c_i$。保证没有重边和自环。

输出$m$行，第$i$行输出一个整数$k_i$，$k_i=1,2,3$分别表示第$i$根绳子总是总是松弛、总是绷紧、时而绷紧时而松弛。

样例说明

• 以节点$1$作为起点时，第$1,2,3$条边的绳子绷紧；
• 以节点$2$作为起点时，第$1,2,3,4,5$条边的绳子绷紧；
• 以节点$3$作为起点时，第$1,2,3,4$条边的绳子绷紧；
• 以节点$4$作为起点时，第$1,2,3,5$条边的绳子绷紧；

数据规模与约定

对于20%的数据，\(n\leq 10\);

对于50%的数据，\(n\leq 100\);

对于100%的数据，$1\leq n\leq500,\quad 0\leq m\leq n(n-1)/2,\quad 1\leq a_i,b_i\leq n,\quad 1\leq c_i\leq 10^6$。