// Problem: Egor in the Republic of Dagestan
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1407E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define Rep(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define Per(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)<(y)?(y):(x))
#define DEBUG 1
namespace FastIO{
#define isdigit(x) (x>='0'&&x<='9')
#define MAXSIZE (1<<20)
#define PREC 6
#define FileIO(fn) freopen(fn".in","r",stdin),freopen(fn".out","w",stdout)
	char buf[MAXSIZE],pbuf[MAXSIZE],*pp=pbuf,*p1,*p2;
	struct CONDES{
#if DEBUG
#else
		CONDES(){p1=buf;p2=buf;pp=pbuf;}
		~CONDES(){fwrite(pbuf,1,pp-pbuf,stdout);}
#endif
	}_CONDES;
	inline char gc(){
#if DEBUG
		return getchar();
#endif
		if(p1==p2)p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);
		return p1==p2?' ':*p1++;
	}
	template<class T>
	inline void read(T&x){
		double tmp=1;
		bool sign=0;x=0;
		char c=gc();
		for(;!isdigit(c);c=gc())if(c=='-')sign=1;
		for(;isdigit(c);c=gc())x=x*10+(c-'0');
		if(c=='.')for(c= gc();isdigit(c);c=gc())tmp/=10.0,x+=tmp*(c-'0');
		if(sign)x=-x;
	}
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
	inline void read(char *s){
		char c=gc();
		for(;blank(c);c=gc());
		for(;!blank(c);c=gc())*s++=c;
		*s=0;
	}
	inline void read(char &c){for(c=gc();blank(c);c=gc());}
	template<class T,class...Args>
	inline void read(T&x,Args&...args){read(x);read(args...);}
	inline void pc(const char &c){
#if DEBUG
		putchar(c);
#else
		if(pp-pbuf==MAXSIZE)fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;
		*pp++=c;
#endif
	}
	template<class T>
	inline void write(T x){
		if(x<0)x=-x,pc('-');
		static int sta[35];
		int top=0;
		do{sta[top++]=x%10,x/=10;}while(x);
		while(top)pc(sta[--top]+'0');
	}
	inline void write(char* s){while(*s)pc(*s++);}
	inline void write(const char* s){while(*s)pc(*s++);}
	inline void write(char c){pc(c);}
	template<class T>
	inline void write_float(T x,int prec=PREC){
		if(x==0){pc('0');pc('.');while(prec--)pc('0');return;}
		if(x<0)x=-x,pc('-');
		static int sta[35];
		int top=0;T pw=pow(10,prec);
		x=round(pw*x);
		if(x<pw)pc('0'),pc('.');
		do{sta[top++]=((ull)x)%10;x=(x-(ull)x%10)/10.0;}while(x>=1.0);
		while(top){pc(sta[--top]+'0');if(top==prec)pc('.');}
	}
	inline void write(float x){write_float(x);}
	inline void write(double x){write_float(x);}
	inline void write(long double x){write_float(x);}
	template<class T,class...Args>
	inline void write(T x,Args...args){write(x);write(args...);}
};
using namespace FastIO;
const int N=5e5+5;
struct edge{
	int to,nx;
	bool cl;
}e[N];
int hd[N],q[N],l=1,r=1,n,m,ec=0,ans=-1,ds=0;
bool vs[N],ad[N],c[N];
void added(int x,int y,bool z){
	e[++ec]={y,hd[x],z};
	hd[x]=ec;
}
signed main(){
	int i,x,y,z;
	read(n,m);
	if(n==1){write("0\n0");return 0;}
	for(i=1;i<=m;i++){
		read(x,y,z);
		added(y,x,z);
	}
	ad[n]=1;
	q[r++]=n;
	while(r>l){
		x=q[l++];
		if(x==1)break;
		for(i=hd[x];i;i=e[i].nx){
			y=e[i].to;
			if(ad[y])continue;
			if(vs[y]&&c[y]==e[i].cl){
				ds++;q[r++]=y;ad[y]=1;
				if(y==1&&ans==-1)ans=ds;
			}else if(!vs[y])vs[y]=1,c[y]=e[i].cl^1;
		}
	}
	write(ans,'\n');
	for(i=1;i<=n;i++)write(c[i]);
	return 0;
}

有一个点最短路长度错了