In the following explanations, let $g(i)$ denote the integer we should output for vertex $i$.

Subtask 1: every character is $a$

Because every edge has value $a$, all $f(1,i)$ are prefixes of $a^{\infty}$. So a string is lexicographically smaller than another if it has shorter length. Thus, $g(i)$ equals the minimum distance from $1$ to $i$, which can be computed using BFS.

Subtask 2: every character is $a$ or $b$

In this subtask, $f(1,i)$ can contain more than one distinct character. However, there are strings that $f(1,i)$ definitely cannot equal due to the graph being undirected. For example, $f(1,i)$ cannot equal $ab$, because there is a path from $1$ to $i$ that is lexicographically smaller ($aaab$) resulting from traversing the edge with value $a$ thrice instead of once. In the general case, if $f(1,i)$ exists, the characters in it must be in non-increasing order, such as $zzrraa$. If this were not the case, we could get a lexicographically smaller string by traversing the edge prior to the first increase two more times.

For subtask 2 in particular, we know that all $f(1,i)$ are of the form $b^{x}a^{y}$. Assume that the graph contains an edge with value $a$. Let's first find the distance $d$ from $1$ to the closest vertex adjacent to an $a$ using BFS. Then if $g(i)=l$ where $l\ge 0$,

• If $l\le d$, then $f(i)=b^l$.
• Otherwise, $f(i)=b^da^{l-d}$. Obviously $f(i)$ must start with at least $d$ occurrences of $b$, and $f(i)$ cannot start with $b^{d+1}$ because then we could get a smaller string by first traversing a path producing $b^da$ and then traversing any path from the endpoint of the first path to $i$.

So we know that $g(i)$ equals the minimum $l$ such there is a path from $1$ to $i$ producing the length-$l$ prefix of $b^da^{\infty}$, or $-1$ if no such path exists. We can compute $g$ using a modified BFS.

Botao Yuan's C++ code:

#include <bits/stdc++.h>
using namespace std; 
 
void solve() {
    int n, m; 
    cin >> n >> m; 
 
    vector<vector<pair<int, char>>> g(n);
    for (int i = 0; i < m; ++i) {
        int x, y; 
        char c; 
        cin >> x >> y >> c; 
 
        x--; y--; 
 
        assert(c == 'a' || c == 'b'); 
 
        g.at(x).emplace_back(y, c); 
        g.at(y).emplace_back(x, c); 
    }
 
    int first_a = 1e9; 
 
    queue<int> q; 
    vector<int> dist(n, -1); 
    dist.at(0) = 0; 
    q.push(0);
 
    while (!q.empty()) {
        auto x = q.front(); 
        q.pop(); 
 
        for (auto [y, c]: g.at(x)) {
            if (c == 'a') first_a = min(first_a, dist.at(x)); 
        }
 
        for (auto [y, c]: g.at(x)) {
            if (dist.at(y) == -1) {
                dist.at(y) = dist.at(x) + 1; 
                q.push(y); 
            }
        }
    }
 
    dist = vector<int>(n, -1); 
    dist.at(0) = 0; 
    q.push(0); 
 
    while (!q.empty()) {
        auto x = q.front(); 
        q.pop(); 
 
        for (auto [y, c]: g.at(x)) {
            if ((c == 'a' || (c == 'b' && dist.at(x) < first_a)) && dist.at(y) == -1) {
                dist.at(y) = dist.at(x) + 1; 
                q.push(y); 
            }
        }
    }
 
    for (int i = 0; i < n; ++i) {
        cout << dist.at(i) << " \n"[i + 1 == n]; 
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t; 
    cin >> t; 
    while (t--) {
        solve(); 
    }
}

Subtask 3: $O(N(N + M))$

Let $S_l$ denote the lexicographically minimum string produced by a path of length $l$ starting at $1$ and ending at any vertex. Then due to the graph being undirected, $S_{l}$ is always a prefix of $S_{l+1}$, and the characters of $S_l$ are always in non-increasing order. This is a generalization of our logic from subtask 2 (in that subtask, $S_l$ was the length-$l$ prefix of $b^da^{\infty}$).

Similarly as in subtask 2, if for some vertex $i$ we have $g(i)=l$, we must have $f(1,i)=S_l$ or we'll reach a contradiction (we can't have $f(1,i)>S_l$, or we'll be able to produce a lexicographically smaller string with the same endpoint). Let $V_l$ denote the set of all vertices that can be endpoints of $S_l$. Then for each $i$, $g(l)$ equals the minimum $l$ such that $i\in V_l$, or $-1$ if no such path exists.

We may observe that $g(i)<N$; otherwise, $f(1,i)$ would contain a cycle, and we could remove that cycle to produce a lexicographically smaller $f(1,i)$. So it suffices to compute $S_l$ and $V_l$ for $l=0\dots N-1$, which we can do in $O(N+M)$ time per value of $l$. Specifically, we calculate the minimum value $c_l$ over all edges adjacent to $V_l$, set $S_{l+1}=S_l+c_l$, and then add the vertices on the opposite side of all edges with value $c_l$ to $V_{l+1}$.

 
#include "bits/stdc++.h"
#define endl '\n'
#define f first
#define s second
using namespace std;

const int N = 2e5 + 5, A = 28;
int n, m;
vector<pair<int, int>> g[N];
int ans[N];

void ac() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) ans[i] = -1, g[i].clear();
    for (int i = 1; i <= m; i++) {
        int a, b;
        char x;
        cin >> a >> b >> x;
        int c = (x - 'a');  // converting characters to integers
        g[a].push_back({c, b});
        g[b].push_back({c, a});
    }
    vector<bool> active(n + 1);
    active[1] = 1;
    for (int l = 0; l < n; ++l) {
        int min_edge = A;
        for (int i = 1; i <= n; ++i)
            if (active[i]) {  // finding min edge to take
                if (ans[i] == -1) ans[i] = l;
                for (auto j : g[i]) min_edge = min(min_edge, j.f);
            }
        vector<bool> next_active(n + 1);
        for (int i = 1; i <= n; ++i)
            if (active[i]) {
                for (auto j : g[i]) {
                    if (j.f == min_edge) {  // extending string
                        next_active[j.s] = 1;
                    }
                }
            }
        swap(next_active, active);
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) ac();
}

Full Solution: $O(N + M)$

Let's optimize the previous solution by reducing the sum of the sizes of the sets $V_l$. In particular, we can define $W_l=V_l\setminus (\bigcup_{0\le l'<l}V_{l'})$ and have the solution be exactly the same as before but replacing $V_l$ with $W_l$. Note that every vertex belongs to at most one set $W_l$, which bounds the runtime. Once we reach $l$ such that $W_l$ is empty, then we can terminate.

It remains to show why the new solution computes the same values of $S_l$ and $W_l$ as the old one. This can be shown by induction. Assuming $S_l$ and $W_l$ are computed correctly and $W_l$ is nonempty, then we can show that $S_{l+1}$ and $W_{l+1}$ are computed correctly:

• correctness of $c_l$ and $S_{l+1}$: for any vertex in $W_l$, the minimum value adjacent to it is at most the minimum value adjacent to any vertex in $\bigcup_{0\le l'<l}V_{l'}$. This means that the minimum value adjacent to $W_l$ equals the minimum value adjacent to $V_l$.
• correctness of $W_{l+1}$: every vertex in $W_{l+1}$ must be the result of starting in a vertex in $W_l$ and traversing an edge with value $c_l$

#include "bits/stdc++.h"
#define endl '\n'
#define f first
#define s second
using namespace std;
 
const int N = 2e5 + 5, A = 28;
int n, m;
vector<pair<int, int>> g[N];
int ans[N];
 
void ac() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) ans[i] = -1, g[i].clear();
    for (int i = 1; i <= m; i++) {
        int a, b;
        char x;
        cin >> a >> b >> x;
        int c = (x - 'a');  // converting characters to integers
        g[a].push_back({c, b});
        g[b].push_back({c, a});
    }
    ans[1] = 0;
    vector<int> active;
    active.push_back(1);
    while (active.size()) {
        int min_edge = A;
        for (int i : active) {  // finding min edge to take
            for (auto j : g[i]) min_edge = min(min_edge, j.f);
        }
        vector<int> next_active;
        for (int i : active) {
            for (auto j : g[i]) {
                if (ans[j.s] == -1 && j.f == min_edge) {  // extending string
                    ans[j.s] = ans[i] + 1;
                    next_active.push_back(j.s);
                }
            }
        }
        swap(next_active, active);
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
}
 
int main() {
    int t;
    cin >> t;
    while (t--) ac();
}