#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T& x) {
  x = 0;
  char ch = getchar();
  long long f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  x *= f;
}
template <typename T, typename... Args>
void read(T& first, Args&... args) {
  read(first);
  read(args...);
}
template <typename T>
void write(T arg) {
  T x = arg;
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
template <typename T, typename... Ts>
void write(T arg, Ts... args) {
  write(arg);
  if (sizeof...(args) != 0) {
    putchar(' ');
    write(args...);
  }
}
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
const int N = 4e5 + 5;
int head[N], cnt;
struct Node {
  int t, next, w;
} edge[N << 1];
void add(int f, int t, int w) {
  edge[cnt].t = t;
  edge[cnt].w = w;
  edge[cnt].next = head[f];
  head[f] = cnt++;
}
int n, m;
struct node {
  int v;
  int value;
  node(int a, int b) : v(a), value(b){};
  bool operator<(const node& no) const { return value > no.value; }
};
int vis[N];
int dis[N << 1][2];
void dijkstra(int s) {
  memset(dis, 0x3f3f3f3f, sizeof(dis));
  priority_queue<node> q;
  dis[s][0] = dis[s][1] = 0;
  q.push(node(s, 0));
  while (!q.empty()) {
    node no = q.top();
    q.pop();
    int u = no.v;
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int v = edge[i].t, c = edge[i].w;
      int dd = max(dis[u][0], dis[u][1]);
      if (dis[v][c] > dd + 1) {
        dis[v][c] = dd + 1;
        int cur = max(dis[v][0], dis[v][1]);
        if (cur < 0x3f3f3f3f) q.push(node(v, cur));
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  memset(head, -1, sizeof(head));
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, t;
    cin >> u >> v >> t;
    add(v, u, t);
  }
  dijkstra(n);
  if (max(dis[1][0], dis[1][1]) < 0x3f3f3f3f)
    cout << max(dis[1][0], dis[1][1]) << endl;
  else
    cout << -1 << endl;
  for (int i = 1; i <= n; i++)
    if (dis[i][0] > dis[i][1])
      cout << 0;
    else
      cout << 1;
  cout << endl;
}
