CF1407E.Egor in the Republic of Dagestan

Egor is a famous Russian singer, rapper, actor and blogger, and finally he decided to give a concert in the sunny Republic of Dagestan.

There are $n$ cities in the republic, some of them are connected by $m$ directed roads without any additional conditions. In other words, road system of Dagestan represents an arbitrary directed graph. Egor will arrive to the city $1$, travel to the city $n$ by roads along some path, give a concert and fly away.

As any famous artist, Egor has lots of haters and too annoying fans, so he can travel only by safe roads. There are two types of the roads in Dagestan, black and white: black roads are safe at night only, and white roads — in the morning. Before the trip Egor's manager's going to make a schedule: for each city he'll specify it's color, black or white, and then if during the trip they visit some city, the only time they can leave it is determined by the city's color: night, if it's black, and morning, if it's white. After creating the schedule Egor chooses an available path from $1$ to $n$, and for security reasons it has to be the shortest possible.

Egor's manager likes Dagestan very much and wants to stay here as long as possible, so he asks you to make such schedule that there would be no path from $1$ to $n$ or the shortest path's length would be greatest possible.

A path is one city or a sequence of roads such that for every road (excluding the first one) the city this road goes from is equal to the city previous road goes into. Egor can move only along paths consisting of safe roads only.

The path length is equal to the number of roads in it. The shortest path in a graph is a path with smallest length.

叶戈尔是一位著名的俄罗斯歌手、说唱歌手、演员和博主，他最终决定在阳光明媚的达吉斯坦共和国举办一场演唱会。

达吉斯坦共和国有 $n$ 座城市，其中一些城市由 $m$ 条有向道路连接，且这些道路没有任何额外限制。换言之，达吉斯坦的道路系统构成一个任意的有向图。叶戈尔将抵达第 $1$ 号城市，沿某条路径经由道路前往第 $n$ 号城市，在那里举办演唱会后离开。

作为任何一位著名艺术家，叶戈尔拥有大量黑粉和过于狂热的粉丝，因此他只能行走在“安全道路”上。达吉斯坦的道路分为两类：黑色道路与白色道路。黑色道路仅在夜间安全，白色道路仅在清晨安全。出发前，叶戈尔的经纪人将制定一份日程安排：为每座城市指定一种颜色（黑色或白色）；之后，若旅行途中访问某座城市，则离开该城市的唯一允许时间即由该城市的颜色决定：若为黑色，则只能在夜间离开；若为白色，则只能在清晨离开。日程安排确定后，叶戈尔将选择一条从 $1$ 到 $n$ 的可行路径；出于安全考虑，该路径必须是可能的最短路径。

叶戈尔的经纪人非常喜爱达吉斯坦，希望尽可能长时间地留在这里，因此他请你设计这样一份日程安排，使得：要么从 $1$ 到 $n$ 根本不存在可行路径，要么所有可行路径中最短路径的长度达到最大可能值。

一条路径是指单个城市，或是一系列道路组成的序列，使得对于该序列中除第一条外的每条道路，其起点城市恰好等于前一条道路的终点城市。叶戈尔只能沿全部由安全道路构成的路径移动。

路径的长度定义为其中所含道路的数量。图中的最短路径即为长度最小的路径。

The first line contains two integers $n$, $m$ ($1 \leq n \leq 500000$, $0 \leq m \leq 500000$) — the number of cities and the number of roads.

The $i$-th of next $m$ lines contains three integers — $u_i$, $v_i$ and $t_i$ ($1 \leq u_i, v_i \leq n$, $t_i \in {0, 1}$) — numbers of cities connected by road and its type, respectively ($0$ — night road, $1$ — morning road).

第一行包含两个整数 $n$、$m$（$1 \leq n \leq 500000$，$0 \leq m \leq 500000$）—— 分别表示城市的数量和道路的数量。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $t_i$（$1 \leq u_i, v_i \leq n$，$t_i \in \{0, 1\}$）—— 分别表示该道路所连接的两座城市的编号及其类型（$0$ 表示夜间道路，$1$ 表示清晨道路）。

In the first line output the length of the desired path (or $-1$, if it's possible to choose such schedule that there's no path from $1$ to $n$).

In the second line output the desired schedule — a string of $n$ digits, where $i$-th digit is $0$, if the $i$-th city is a night one, and $1$ if it's a morning one.

If there are multiple answers, print any.

第一行输出所求路径的长度（若存在一种调度方案使得从城市 $1$ 到城市 $n$ 不存在路径，则输出 $-1$）。

第二行输出所求的调度方案——一个长度为 $n$ 的数字字符串，其中第 $i$ 位数字为 $0$ 表示第 $i$ 个城市是“夜间城市”，为 $1$ 表示第 $i$ 个城市是“清晨城市”。

若存在多个合法答案，输出任意一个即可。

For the first sample, if we paint city $1$ white, the shortest path is $1 \rightarrow 3$. Otherwise, it's $1 \rightarrow 2 \rightarrow 3$ regardless of other cities' colors.

For the second sample, we should paint city $3$ black, and there are both black and white roads going from $2$ to $4$. Note that there can be a road connecting a city with itself.

对于第一个样例，如果我们把城市 $1$ 涂成白色，则最短路径为 $1 \rightarrow 3$；否则，无论其他城市的颜色如何，最短路径均为 $1 \rightarrow 2 \rightarrow 3$。

对于第二个样例，我们应该把城市 $3$ 涂成黑色，且从城市 $2$ 到城市 $4$ 同时存在黑色道路和白色道路。注意：可能存在连接某个城市与其自身的道路。