该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

随着时间的流逝，刚进入大学的大一懵懂小生如今已经变成了大四老登，要毕业的他不得不开始实习上班。

某天，瓢泼大雨，老登在公司门口摔了一跤，好不容易爬到工位，迎接他的是没人愿意做、于是顺手丢给实习生的 $\texttt{dirty work}$，以及没有统一口径随着时间反复横跳的需求。

每当老登做完手头的工作，向需求方询问接下来该干什么时，得到的回答都可能截然不同。

遗憾的是，需求方自始至终都没有想好过需要什么。只有在收到询问后，他们才会灵机一动，现场构思出一个需求。于是，老登只能一边盯着时间，一边在各个工作阶段之间被需求踢来踢去。

终于，他崩溃了。

发出了：

“这 $\beta$ 班谁爱上谁上。”

的声音。

在历经千辛万苦完成工作之后，老登终于下班了，但饿了一天的老登因为工资很低只能去便利店买点泡面饱腹。

然而刚刚走出便利店门口，感到疲倦的他揉了揉眼睛，却发现自己回到了开始工作的第一天。

好消息是，上一次工作的记忆并没有消失。虽然需求方依旧会现场发挥，但经历过完整的一轮折磨后，老登已经彻底摸清了他们的规律。

为了尽快完成工作下班加训，他带着这些记忆，再次踏入了公司。

Oh please don't let me die, Waiting for your touch.

No don't give up on life, This endless dead end.

题目描述

为了方便管理，老登把整个工作拆成了 $n$ 个工作阶段，编号为 $1,2,\dots,n$。他需要从阶段 $1$ 开始，最终推进到阶段 $n$。

老登在时刻 $0$ 位于工作阶段 $1$，工作完成当且仅当首次达到工作阶段 $n$。

对于每个工作阶段 $u$，需求方一共可能给出 $d_u$ 种不同的需求。为了方便描述，将这些需求依次编号为 $0,1,\dots,d_u-1$。

如果老登在整数时刻 $t$ 位于工作阶段 $u$，并在此时向需求方询问接下来的安排，那么需求方现编出的恰好是第 $t \bmod d_u$ 种需求。

第 $j$ 种需求会花费老登 $w_{u, j}$ 单位时间，并在完成后进入工作阶段 $v_{u, j}$。一旦老登选择向需求方询问，他必须立刻开始执行需求方在该时刻提出的需求。

老登可以选择暂时不询问，而是在当前工作阶段摸鱼等待任意非负整数时间。

请你帮助老登计算一下从工作阶段 $1$ 开始，最早需要多少时间才能完成工作。

并且老登还希望知道，对于每种需求是否有可能出现在一种最快完成工作的方案中。

输入格式

第一行包含两个整数 $n,m$（$2 \le n\le 2\times 10^5$，$n-1\le m\le 2\times 10^5$），分别表示工作阶段的数量和需求的总数。

接下来 $m$ 行，每行包含三个整数 $u,v,w$（$1\le u, v\le n$，$1\le w\le 10^9$），表示工作阶段 $u$ 存在一种需求，需要花费 $w$ 的时间完成，并且在完成后进入工作阶段 $v$。

对于同一个工作阶段 $u$，它的所有需求按照在输入中出现的先后顺序，依次编号为 $0, 1, \dots,d_u - 1$。

数据保证对于所有 $1\le u<n$，都有 $d_u\ge 1$。

数据保证从工作阶段 $1$ 出发可以到达工作阶段 $n$。

输出格式

第一行输出一个整数 $T$，表示老登最早完成工作所需要的时间。

第二行输出一个长度为 $m$ 的 $01$ 串 $s$，对于输入的第 $i$ 个需求，如果存在一种最快完成工作的方案执行过此需求，则 $s_i=1$，否则 $s_i=0$。

样例

3 5
1 2 1
1 2 1
2 2 1
2 2 1
2 3 1

3
11011