#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long sum = 0, ff = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') {
      ff = -1;
    }
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    sum = sum * 10 + ch - 48;
    ch = getchar();
  }
  return sum * ff;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 1000007;
int n, m;
struct edge {
  int from, to, dis, next;
} e[N], a[N];
int he[N], cnt;
void add(int u, int v, int w) {
  e[++cnt].from = u;
  e[cnt].to = v;
  e[cnt].dis = w;
  e[cnt].next = he[u];
  he[u] = cnt;
}
bool cmp(edge x, edge y) {
  if (x.from == y.from) return x.to < y.to;
  return x.from < y.from;
}
int col[N];
queue<int> q;
struct node {
  int pos, dis;
};
queue<node> que;
bool vis[N];
int bfs() {
  que.push((node){n, 0});
  vis[n] = true;
  while (!que.empty()) {
    node now = que.front();
    que.pop();
    if (now.pos == 1) return now.dis;
    for (int i = he[now.pos]; i; i = e[i].next) {
      int v = e[i].to;
      if (vis[v]) continue;
      if (col[v] == -1 || col[v] == 1 - e[i].dis)
        col[v] = 1 - e[i].dis;
      else {
        vis[v] = true;
        que.push((node){v, now.dis + 1});
      }
    }
  }
  return -1;
}
map<pair<int, int>, bool> mp;
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    a[i].from = read(), a[i].to = read(), a[i].dis = read();
    add(a[i].to, a[i].from, a[i].dis);
  }
  memset(col, -1, sizeof(col));
  write(bfs()), puts("");
  for (int i = 1; i <= n; i++)
    if (col[i] == -1)
      printf("0");
    else
      write(col[i]);
  return 0;
}
