#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define int ll
#define endl '\n'
#define vll vector<ll>
#define input(arr) \
    for (auto& i : arr) cin >> i
#define print(arr) \
    for (auto& i : arr) cout << i << ' '; cout << '\n'
#define INF LLONG_MAX
#define YARAB_ACCEPT ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

ll dx[] = {0, 0, -1, 1, 1, 1, -1, -1};
ll dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const ll N = 2e5 + 5;

struct Edge { ll to; char c; };

vector<Edge> adj[N];

void solve() {
    ll n, m; cin >> n >> m;

    for (ll i = 0; i < m; ++i) {
        ll u, v; cin >> u >> v;
        char c; cin >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    vll dist(n + 1, -1);
    queue<ll> q;
    dist[n] = 0;
    q.push(n);

    while (!q.empty()) {
        ll u = q.front(); q.pop();

        for (const auto& edge : adj[u]) {
            if (dist[edge.to] == -1) {
                dist[edge.to] = dist[u] + 1;
                q.push(edge.to);
            }
        }
    }

    vll curr = {1}, parent(n + 1, -1), vis(n + 1, false);
    string s = "";
    vis[1] = 1;

    for (int step = 0; step < dist[1]; ++step) {
        char min_char = 'z' + 1;

        for (auto u : curr) {
            for (const auto& edge : adj[u]) {
                if (dist[edge.to] == dist[u] - 1) {
                    min_char = min(min_char, edge.c);
                }
            }
        }

        s.push_back(min_char);

        vll next_curr;

        for (auto u : curr) {
            for (const auto& edge : adj[u]) {
                if (dist[edge.to] == dist[u] - 1 && edge.c == min_char) {
                    if (!vis[edge.to]) {
                        vis[edge.to] = 1;
                        parent[edge.to] = u;
                        next_curr.push_back(edge.to);
                    }
                }
            }
        }

        swap(curr, next_curr);
    }

    vll path;
    ll curr_node = n;

    while (curr_node != -1) {
        path.push_back(curr_node);
        curr_node = parent[curr_node];
    }
    reverse(path.begin(), path.end());

    cout << dist[1] << '\n';

    for (ll i = 0; i < path.size(); ++i) {
        cout << path[i] << ' ';
    }

    cout << '\n';
    cout << s << '\n';
}

signed main() {
    YARAB_ACCEPT
    ll t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}