#include <bits/stdc++.h>
using namespace std;
ostream& operator<<(ostream& str, const pair<long long, long long>& p) {
  str << p.first << " " << p.second;
  return str;
}
template <typename T>
void join(T& arr, string sep) {
  bool first = true;
  for (auto t : arr) {
    if (first) {
      first = false;
      cout << t;
    } else {
      cout << sep << t;
    }
  }
  cout << "\n";
}
const long long md = 1e9 + 7;
long long MOD(long long x) {
  long long r = x % md;
  if (r < 0) {
    r += md;
  }
  return r;
}
void solve() {
  long long n, m;
  cin >> n >> m;
  vector<long long> types(n);
  vector<vector<pair<long long, long long>>> g(n);
  for (long long i = 0; i < (long long)(m); ++i) {
    long long u, v, t;
    cin >> u >> v >> t;
    u--;
    v--;
    g[v].push_back({u, t});
  }
  long long s = 0, e = n - 1;
  vector<vector<long long>> dist(n, vector<long long>(2, 1e18));
  vector<vector<long long>> visited(n, vector<long long>(2, 0));
  vector<pair<long long, long long>> cur = {{e, 0}, {e, 1}};
  long long d = 0;
  while (!cur.empty()) {
    vector<pair<long long, long long>> nxt;
    for (auto& p : cur) {
      long long u = p.first;
      long long t = p.second;
      dist[u][t] = d;
      if (dist[u][1 - t] == 1e18) continue;
      for (auto& p2 : g[u]) {
        long long v = p2.first;
        long long t2 = p2.second;
        if (visited[v][t2]) continue;
        visited[v][t2] = 1;
        nxt.push_back({v, t2});
      }
    }
    d++;
    cur = nxt;
  }
  for (long long u = 0; u < (long long)(n); ++u) {
    if (dist[u][0] > dist[u][1])
      types[u] = 0;
    else
      types[u] = 1;
  }
  long long len = max(dist[0][0], dist[0][1]);
  if (len == 1e18) len = -1;
  cout << len << endl;
  join(types, "");
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  for (int t = 1; t <= tt; t++) {
    solve();
  }
  return 0;
}
