#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000005;

struct Edge {
  int u, v, next;
  char w;
} e[maxn << 1], f[maxn << 1];
vector<tuple<int, int, string>> E;
int head[maxn], cnt;
void add(int u, int v, char w) {
  e[++cnt].v = v;
  e[cnt].w = w;
  e[cnt].next = head[u];
  head[u] = cnt;
}
int headf[maxn], cntf;
void addf(int u, int v, char w) {
  f[++cntf].v = v;
  f[cntf].w = w;
  f[cntf].next = headf[u];
  headf[u] = cntf;
}

int n, m, nc;

void make_graph() {
  for (auto P : E) {
    int u = get<0>(P);
    int v = get<1>(P);
    string w = get<2>(P);
    int lst = u;
    for (int i = 0; i < w.length(); ++i) {
      int x = u, y = v;
      if (i != 0) x = lst;
      if (i != w.length() - 1) {
        y = lst = ++nc;
      }
      add(x, y, w[i]);
      addf(y, x, w[i]);
    }
  }
}

int dis1[maxn], disn[maxn];
void solve_dis1(int s) {
  queue<int> q;
  fill(dis1 + 1, dis1 + 1 + nc, 0x3f3f3f3f);
  dis1[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (dis1[v] > dis1[u] + 1) {
        dis1[v] = dis1[u] + 1;
        q.push(v);
      }
    }
  }
  return;
}
void solve_disn(int s) {
  queue<int> q;
  fill(disn + 1, disn + 1 + nc, 0x3f3f3f3f);
  disn[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = headf[u]; i; i = f[i].next) {
      int v = f[i].v;
      if (disn[v] > disn[u] + 1) {
        disn[v] = disn[u] + 1;
        q.push(v);
      }
    }
  }
  return;
}

bool vis[maxn];
string bfs(bool min_dis) {
  fill(vis, vis + maxn, false);
  string ans;
  vector<int> now, nxt;
  now.push_back(1);
  while (true) {
    char mn = 127;
    for (auto u : now) {
      for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (min_dis) if (ans.length() + disn[v] + 1 > dis1[n])
          continue;
        if (!min_dis) if (disn[v] >= 0x3f3f3f3f)
          continue;
        if (e[i].w < mn) {
          for (auto x : nxt) vis[x] = false;
          nxt.clear();
          mn = e[i].w;
          vis[v] = true;
          nxt.emplace_back(v);
        } else if (e[i].w == mn) {
          if (!vis[v]) {
            vis[v] = true;
            nxt.emplace_back(v);
          }
        }
      }
    }
    ans += mn;
    if (vis[n]) break;
    for (auto x : nxt) vis[x] = false;
    now.swap(nxt);
    nxt.clear();
  }
  return ans;
}

int main() {
  //freopen("path.in", "r", stdin);
  //freopen("path.out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    string w;
    cin >> u >> v >> w;
    E.emplace_back(u, v, w);
  }
  nc = n;
  make_graph();
  solve_dis1(1), solve_disn(n);
  cout << bfs(true) << ' ' << bfs(false) << endl;
  return 0;
}