#include <bits/stdc++.h>
using namespace std;
template <typename G1, typename G2 = G1, typename G3 = G1>
struct triple {
  G1 first;
  G2 second;
  G3 T;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<pair<long long, long long>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, t;
    cin >> x >> y >> t;
    --x;
    --y;
    g[y].push_back({t, x});
  }
  const int oo = 1e9;
  vector<vector<bool>> s(2, vector<bool>(n));
  s[0][n - 1] = s[1][n - 1] = true;
  vector<vector<int>> p(2, vector<int>(n));
  vector<vector<int>> d(2, vector<int>(n, oo));
  d[0][n - 1] = d[1][n - 1] = 0;
  vector<int> t(n), h(n, oo);
  t[n - 1] = 2;
  h[n - 1] = 0;
  queue<pair<long long, long long>> q;
  q.push({0, n - 1});
  q.push({1, n - 1});
  while (!q.empty()) {
    pair<long long, long long> c = q.front();
    q.pop();
    for (auto v : g[c.second])
      if (!s[v.first][v.second]) {
        s[v.first][v.second] = true;
        d[v.first][v.second] = h[c.second] + 1;
        p[v.first][v.second] = c.second;
        ++t[v.second];
        if (t[v.second] == 2) {
          q.push({0, v.second});
          q.push({1, v.second});
          h[v.second] = max(d[0][v.second], d[1][v.second]);
        }
      }
  }
  vector<int> col(n, -1);
  cout << (h[0] == oo ? -1 : h[0]) << '\n';
  if (h[0] == oo) {
    for (int i = 0; i < n; i++) col[i] = (d[1][i] == oo);
  } else {
    int b = 0;
    while (b != n - 1) {
      int a = (d[1][b] > d[0][b]);
      col[b] = a;
      b = p[a][b];
    }
  }
  for (int i = 0; i < n; i++)
    if (col[i] == -1) col[i] = (d[1][i] > d[0][i]);
  for (int i = 0; i < n; i++) cout << col[i];
  cout << '\n';
  return 0;
}
