#include <bits/stdc++.h>
using namespace std;
const long long zero = 0;
const long long one = 1;
const long long INF = 9223372036854775807;
const int inINF = 2147483647;
const long long MOD = 1000000007;
const long long MOD2 = 998244353;
void Yes() { printf("Yes\n"); }
void No() { printf("No\n"); }
void YES() { printf("YES\n"); }
void NO() { printf("NO\n"); }
int main() {
  int N, M;
  cin >> N >> M;
  vector<map<int, int>> G(N);
  int u, v, t;
  for (int i = 0; i < M; i++) {
    cin >> v >> u >> t;
    u--;
    v--;
    if (!G[u].count(v)) {
      G[u][v] = t + 1;
    } else {
      if (t == 0) {
        if (G[u][v] % 2 == 0) {
          G[u][v]++;
        }
      } else {
        if (G[u][v] < 2) {
          G[u][v] += 2;
        }
      }
    }
  }
  queue<int> q;
  vector<bool> used(N, false);
  vector<int> chosen(N, -1);
  vector<int> d(N, -1);
  used[N - 1] = true;
  chosen[N - 1] = 0;
  d[N - 1] = 0;
  q.push(N - 1);
  while (!q.empty()) {
    int w = q.front();
    q.pop();
    bool c = false;
    for (pair<int, int> z : G[w]) {
      if (used[z.first]) continue;
      if (z.second == 3) {
        q.push(z.first);
        used[z.first] = true;
        d[z.first] = d[w] + 1;
        if (chosen[z.first] == -1) chosen[z.first] = 0;
        if (z.first == 0) c = true;
      } else if (z.second == 2) {
        if (chosen[z.first] == -1) {
          chosen[z.first] = 0;
        } else if (chosen[z.first] == 0) {
        } else {
          q.push(z.first);
          used[z.first] = true;
          d[z.first] = d[w] + 1;
          if (z.first == 0) c = true;
        }
      } else {
        if (chosen[z.first] == -1) {
          chosen[z.first] = 1;
        } else if (chosen[z.first] == 1) {
        } else {
          q.push(z.first);
          used[z.first] = true;
          if (z.first == 0) c = true;
          d[z.first] = d[w] + 1;
        }
      }
    }
    if (c) break;
  }
  if (d[0] == -1) {
    printf("%d\n", -1);
    for (int i = 0; i < N; i++) {
      printf("%d", max(chosen[i], 0));
    }
    cout << endl;
    return 0;
  }
  printf("%d\n", d[0]);
  for (int i = 0; i < N; i++) {
    printf("%d", max(chosen[i], 0));
  }
  cout << endl;
}
