#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int> > badj(n + 1);
  vector<vector<int> > wadj(n + 1);
  int u, v, t;
  for (int i = 0; i < m; i++) {
    cin >> u >> v >> t;
    if (t == 0)
      badj[v].push_back(u);
    else
      wadj[v].push_back(u);
  }
  queue<int> q;
  vector<vector<int> > dist(n + 1, vector<int>(3, n));
  q.push(n);
  dist[n][0] = 0;
  dist[n][1] = 0;
  dist[n][2] = 0;
  int top;
  int _max;
  int tmp_max;
  int prev_max;
  while (!q.empty()) {
    top = q.front();
    q.pop();
    for (int i = 0; i < badj[top].size(); i++) {
      if (dist[badj[top][i]][0] < n) continue;
      dist[badj[top][i]][0] = dist[top][2] + 1;
      if (max(dist[badj[top][i]][0], dist[badj[top][i]][1]) < n) {
        q.push(badj[top][i]);
        dist[badj[top][i]][2] =
            max(dist[badj[top][i]][0], dist[badj[top][i]][1]);
      }
    }
    for (int i = 0; i < wadj[top].size(); i++) {
      if (dist[wadj[top][i]][1] < n) continue;
      dist[wadj[top][i]][1] = dist[top][2] + 1;
      if (max(dist[wadj[top][i]][0], dist[wadj[top][i]][1]) < n) {
        q.push(wadj[top][i]);
        dist[wadj[top][i]][2] =
            max(dist[wadj[top][i]][0], dist[wadj[top][i]][1]);
      }
    }
  }
  _max = max(dist[1][0], dist[1][1]);
  if (_max >= n) _max = -1;
  cout << _max << endl;
  for (int i = 1; i <= n; i++) {
    cout << distance(dist[i].begin(),
                     max_element(dist[i].begin(), dist[i].end()));
  }
  cout << endl;
  cout.flush();
}
