#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
long long n, m, k, t;
vector<pair<long long, long long> > G[500005];
int mp[500005] = {0};
queue<pair<long long, long long> > q;
bool vis[500005] = {0};
int ans[500005] = {0};
int main() {
  std::ios::sync_with_stdio(false);
  cin >> n >> m;
  for (long long i = (0); i < (m); i++) {
    int u, v, w;
    cin >> u >> v >> w;
    G[v].push_back({u, w});
  }
  q.push({n, 0});
  vis[n] = 1;
  int num = 0;
  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    if (u.first == 1) {
      cout << u.second << endl;
      for (long long i = (1); i < (n + 1); i++) {
        if (!vis[i]) {
          if (mp[i] & 1) {
            cout << 1;
          } else {
            cout << 0;
          }
          continue;
        }
        cout << ans[i];
      }
      return 0;
    }
    for (auto to : G[u.first]) {
      int tt = to.first;
      int w = to.second;
      if (vis[tt]) continue;
      if ((mp[tt] & (1 << w))) continue;
      mp[tt] |= (1 << w);
      if (mp[tt] == 3) {
        vis[tt] = 1;
        ans[tt] = w;
        q.push({tt, u.second + 1});
      }
    }
  }
  cout << -1 << endl;
  for (long long i = (1); i < (n + 1); i++) {
    if (mp[i] & 1) {
      cout << 1;
    } else {
      cout << 0;
    }
  }
}
