#include<bits/stdc++.h> using namespace std; const int Maxn=5e5+5; const int INF=0x7fffffff; inline int read() { int x=0; char c=getchar(); for(; c<'0' || c>'9'; c=getchar()); for(; c<='9' && c>='0'; c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x; } struct Node{ int v,z,next; }G[Maxn<<1]; int H[Maxn],n,m,p,rec=INF,ans[Maxn]; bool flg=0,vis[Maxn]; inline void Add(int x,int y,int z) { G[++p]=Node{y,z,H[x]}; H[x]=p; } inline bool Search(int now,int lst,int sum) { if(now==n) { rec=min(rec,sum); return 1; } vis[now]=1; bool b=0; for(int i=0;i<=1;i++) { for(int j=H[now];j;j=G[j].next) if(G[j].z==i && !vis[G[j].v] && !Search(G[j].v,now,sum+1)) { ans[now]=i; b=1; } } if(b) return 1; return 0; } int main() { n=read(),m=read(); if(n>10 || m>40) { cout<<-1<<'\n'; for(int i=1;i<=n;i++) cout<<1; cout<<'\n'; return 0; } for(int i=1,x,y,t;i<=m;i++) { x=read(),y=read(),t=read(); if(x==y) continue; Add(x,y,t); } if(Search(1,1,0)) cout<<rec<<'\n'; else cout<<-1<<'\n'; for(int i=1;i<=n;i++) cout<<ans[i]; cout<<'\n'; return 0; }