#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (const T& x : v) os << x << ' ';
  return os;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v) is >> x;
  return is;
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << h;
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
template <class T>
bool miin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool maax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
const int MOD = 1e9 + 7;
const long long INF = 1e18;
const char nl = '\n';
const double PI = acos(-1);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5 + 5;
vector<int> e[N];
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, m;
  cin >> n >> m;
  if (n == 1) {
    cout << "0\n0\n";
    exit(0);
  }
  for (int i = 0; i < m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    e[v].push_back(2 * u + c);
  }
  vector<int> state(n + 1), color(n + 1), dist(n + 1);
  dist[1] = -1;
  queue<int> bfs;
  bfs.push(n);
  state[n] = 2;
  while (bfs.size()) {
    int v = bfs.front();
    bfs.pop();
    for (int u : e[v]) {
      int c = u % 2;
      u /= 2;
      if (state[u] == 0) {
        color[u] = 1 - c;
        state[u] = 1;
      } else if (state[u] == 1 && color[u] == c) {
        bfs.push(u);
        state[u] = 2;
        dist[u] = dist[v] + 1;
      }
    }
  }
  cout << dist[1] << nl;
  for (int i = 1; i <= n; i++) cout << color[i];
  cout << nl;
}
