#include <bits/stdc++.h>
using namespace std;
long long n, m, pnt[500005], nxt[500005], head[500005], E, len[500005],
    dis[500005][2], col[500005];
long long vis[500005][2];
void add_edge(long long u, long long v, long long w) {
  pnt[E] = v;
  nxt[E] = head[u];
  len[E] = w;
  head[u] = E++;
}
struct node {
  long long u, opt, w;
  bool operator<(node x) const { return w > x.w; }
};
signed main() {
  memset(head, -1, sizeof(head));
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= m; i++) {
    long long u, v, w;
    scanf("%lld%lld%lld", &u, &v, &w);
    add_edge(v, u, w);
  }
  memset(dis, 0x7f, sizeof(dis));
  dis[n][0] = dis[n][1] = 0;
  vis[n][0] = vis[n][1] = 1;
  priority_queue<node> Q;
  Q.push(node{n, 0, 0});
  while (!Q.empty()) {
    node p = Q.top();
    Q.pop();
    long long u = p.u, opt = p.opt;
    for (long long i = head[u]; i != -1; i = nxt[i]) {
      long long v = pnt[i];
      long long ww = len[i];
      if (dis[u][opt] + 1 < dis[v][ww]) {
        dis[v][ww] = dis[u][opt] + 1;
        if (!vis[v][ww]) {
          vis[v][ww] = 1;
          if (vis[v][0] && vis[v][1]) {
            node tmp;
            tmp.u = v;
            if (dis[v][0] < dis[v][1])
              tmp.w = dis[v][1], tmp.opt = 1;
            else
              tmp.w = dis[v][0], tmp.opt = 0;
            Q.push(tmp);
          }
        }
      }
    }
  }
  long long u, w;
  for (long long i = 1; i <= n; i++) {
    if (dis[i][0] < dis[i][1])
      col[i] = 1;
    else
      col[i] = 0;
  }
  if (dis[1][0] > 1e9 || dis[1][1] > 1e9) {
    puts("-1");
  } else if (dis[1][0] > dis[1][1]) {
    printf("%lld\n", dis[1][0]);
    col[1] = 0;
    u = 1;
    w = 0;
  } else {
    printf("%lld\n", dis[1][1]);
    col[1] = 1;
    u = 1;
    w = 1;
  }
  for (long long i = 1; i <= n; i++) {
    if (dis[i][0] < dis[i][1])
      printf("1");
    else
      printf("0");
  }
  return 0;
}
