#include <bits/stdc++.h> using namespace std; int n,m; bool vis[50001]; struct F { int ou[1001]; bool cl,c[1001]; int od,f; } a[50001]; inline int Read() { static int x=0,c=getchar(); for(; c<=47||c>=58; c=getchar()); for(x=0; c>=48&&c<=57; c=getchar()) x=(x<<3)+(x<<1)+(c&15); return x; } int D(int x) { if(x==n) return 0; if(a[x].od==0 || vis[x]==1) return -1; if(a[x].od==1) { a[x].cl=!(a[x].c[1]); return -1; } vis[x]=1; int d[3]; d[1]=d[2]=50001; for(int h=1; h<=2; h++) for(int i=1; i<=a[x].od; i++) if(a[x].c[i]==h-1) { d[0]=D(a[x].ou[i]); if(d[0]!=-1) d[h]=min(d[h],d[0]+1); } int i=0; if(d[1]==50001) i=2; if(d[2]==50001) i++; if(i==3) return -1; if(i) a[x].f=d[i--],a[x].cl=i; else if(d[1]>=d[2]) a[x].f=d[1],a[x].cl=0; else a[x].f=d[2],a[x].cl=1; vis[x]=0; return a[x].f; } int main() { // freopen("flow.in","r",stdin); // freopen("flow.out","w",stdout); n=Read(),m=Read(); for(int i=1; i<=m; i++) { int u=Read(),v=Read(),t=Read(); if(u!=v) a[u].ou[++a[u].od]=v,a[u].c[a[u].od]=t; } printf("%d\n",D(1)); for(int i=1; i<=n; i++) printf("%d",a[i].cl); printf("\n"); return 0; }