#include <bits/stdc++.h> using namespace std; const int N =1e6+10; const int INF =3700; #define LL long long int vi[INF][INF]; inline LL read() { LL 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; int w; int c; }; vector<node> g[N<<1]; int dis[N],ans[N],vis[N]; int n,m; void OUT() { for(int i=1; i<=n; i++) cout<<ans[i]; } void SPFA(int s) { queue<int> q; memset(dis,N,sizeof(dis)); q.push(1),dis[1]=0,vis[1]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0; i<g[u].size(); i++) { int sum1=0,sum2=0; for(int j=0; j<g[u].size(); j++) { if(g[u][j].c==0) sum1++; else if(g[u][j].c==1) sum2++; } if(sum1>=sum2) ans[u]=0; else ans[u]=1; int v=g[u][i].v; int w=g[u][i].w; if(dis[v]>dis[u]+w&&g[u][v].c==ans[u]) { dis[v]=dis[u]+w; if(!vis[v]) { q.push(v); vis[v]=1; } } } } if(dis[n]>=N) { cout<<"-1"<<endl; OUT(); return ; } else { cout<<dis[n]<<endl; OUT(); return ; } } int main() { cin>>n>>m; for(int i=1; i<=m; i++) { LL u,v,c; u=read(),v=read(),c=read(); if(u==v) continue; if(vi[u][v]) { g[u].push_back({v,1,2}); continue; } g[u].push_back({v,1,c}); vi[u][v]=1; } SPFA(1); return 0; }