CF102569D

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>

using namespace std;

vector< vector< pair<int, char> > > neighbours;
vector<int> distToN, previous;
vector<char> previousChar;

int main() {
    int n, m; cin >> n >> m;
    neighbours.resize(1+n);
    for (int i = 0; i < m; ++i) {
        int u, v; char c;
        cin >> u >> v >> c;
        neighbours[u].push_back({v,c});
        neighbours[v].push_back({u,c});
    }

    // bfs
    distToN.resize(1+n);
    distToN[n] = 0;
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        for (auto x : neighbours[q.front()]) {
            if (!distToN[x.first] && x.first != n) {
                q.push(x.first);
                distToN[x.first] = distToN[q.front()] + 1;
            }
        }
        q.pop();
    }

    // bfs
    previous.resize(1+n), previousChar.resize(1+n);
    previous[1] = -1;
    vector<int> currentNodes(1, 1);
    vector<bool> hadNode(1+n); // has been placed in currentNodes before
    hadNode[1] = true;
    for (int d = distToN[1]; d > 0; --d) {
        char minChar = 'z';
        for (int node : currentNodes) {
            for (auto edge : neighbours[node]) {
                if (distToN[edge.first] >= distToN[node]) continue;
                if (edge.second < minChar) minChar = edge.second;
            }
        }

        vector<int> currentNodes2;
        for (int node : currentNodes) {
            for (auto edge : neighbours[node]) {
                if (distToN[edge.first] >= distToN[node]) continue;
                if (edge.second == minChar && !hadNode[edge.first]) { // do not add same node in twice
                    previous[edge.first] = node;
                    previousChar[edge.first] = minChar;
                    currentNodes2.push_back(edge.first);
                    hadNode[edge.first] = true;
                }
            }
        }
        currentNodes = currentNodes2;
    }

    stack<char> s;
    stack<int> t;
    cout << distToN[1] << endl;
    for (int node = n; node != -1; node = previous[node]) {
        t.push(node);
        if (previous[node] != -1) s.push(previousChar[node]);
    }

    while (!t.empty()) {
        cout << t.top() << ' ';
        t.pop();
    }
    cout << endl;
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
    cout << endl;
    return 0;
}