#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 5e5 + 5;
vector<pair<int, int>> g[M][2], rg[M][2];
int num[M], dist[M][2];
int vis[M][2];
int ct[M];
int nd[M][2];
int main() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, t;
    cin >> x >> y >> t;
    if (x == y) continue;
    g[x][t].push_back({y, 0});
    g[x][t].push_back({y, 1});
    rg[y][0].push_back({x, t});
    rg[y][1].push_back({x, t});
  }
  deque<pair<int, int>> dq;
  dq.push_back({1, 0});
  dq.push_back({1, 1});
  dist[1][0] = 1;
  dist[1][1] = 1;
  while (!dq.empty()) {
    auto f = dq.front();
    dq.pop_front();
    for (auto V : g[f.first][f.second]) {
      int ver = V.first, typ = V.second;
      if (!dist[ver][typ]) {
        dist[ver][typ] = dist[f.first][f.second] + 1;
        dq.push_back({ver, typ});
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!dist[i][0]) dist[i][0] = 12345678;
    if (!dist[i][1]) dist[i][1] = 12345678;
  }
  for (int i = 1; i <= n; i++) {
    nd[i][0] = 12345678;
    nd[i][1] = 12345678;
  }
  dq.clear();
  rg[n][0].insert(rg[n][0].end(), rg[n][1].begin(), rg[n][1].end());
  sort(rg[n][0].begin(), rg[n][0].end());
  rg[n][0].erase(unique(rg[n][0].begin(), rg[n][0].end()), rg[n][0].end());
  dq.push_back({n, 0});
  vis[n][0] = 1;
  vis[n][1] = 1;
  nd[n][0] = 0;
  nd[n][1] = 0;
  while (!dq.empty()) {
    vector<pair<int, int>> temp;
    int cd;
    while (!dq.empty()) {
      auto f = dq.front();
      dq.pop_front();
      cd = nd[f.first][f.second];
      for (auto V : rg[f.first][f.second]) {
        int ver = V.first, typ = V.second;
        if (!vis[ver][typ]) {
          temp.push_back({ver, typ});
          vis[ver][typ] = 1;
        }
      }
    }
    map<pair<int, int>, int> activ;
    map<int, int> f, done;
    for (auto V : temp) {
      int ver = V.first, typ = V.second;
      ct[ver]++;
      f[ver]++;
      int mindist = 12345678;
      for (auto Z : rg[ver][typ]) {
        if (!vis[Z.first][Z.second]) {
          mindist = min(mindist, dist[Z.first][Z.second]);
        }
      }
      activ[{ver, typ}] = mindist;
    }
    for (auto V : temp) {
      int ver = V.first, typ = V.second;
      if (f[ver] == 1) {
        if (ct[ver] == 1) {
          num[ver] = 1 - typ;
          continue;
        }
        dq.push_back({ver, typ});
        nd[ver][typ] = cd + 1;
      } else {
        if (done[ver]) continue;
        done[ver] = 1;
        if (activ[{ver, typ}] > activ[{ver, 1 - typ}]) {
          dq.push_back({ver, typ});
          num[ver] = typ;
          nd[ver][typ] = cd + 1;
        } else {
          dq.push_back({ver, 1 - typ});
          num[ver] = 1 - typ;
          nd[ver][1 - typ] = cd + 1;
        }
      }
    }
  }
  int fans = min(nd[1][0], nd[1][1]);
  if (fans > 1e6) fans = -1;
  cout << fans << endl;
  for (int i = 1; i <= n; i++) {
    cout << num[i];
  }
}
