#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int t;
int n;
int m;
vector<vector<pair<int, char>>> graph;
vector<int> res;

int main () {

    freopen ("Path.in", "r", stdin);
    freopen ("Path.out", "w", stdout);

    scanf ("%d", &t);
    for (int index = 1; index <= t; index++) {
        scanf ("%d %d", &n, &m);
        graph.clear();
        graph.resize(n + 1);
        for (int i = 1; i <= m; i++) {
            int u, v;
            char w;
            scanf ("%d %d %c", &u, &v, &w);
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        }

        res.clear();
        res.resize(n + 1, -1);
        res[1] = 0;

        queue<pair<int, char>> q;
        q.emplace(1, 'z' + 1);

        while (!q.empty()) {
            queue<pair<int, char>> p;
            char choose = 'z' + 1;

            while (!q.empty()) {
                int u = q.front().first;
                char c = q.front().second;
                p.push(q.front());
                q.pop();

                for (int i = 0; i < graph[u].size(); i++) {
                    choose = min (choose, graph[u][i].second);
                }
            }

            while (!p.empty()) {
                int u = p.front().first;
                char c = p.front().second;
                p.pop();

                for (int i = 0; i < graph[u].size(); i++) {
                    int v = graph[u][i].first;
                    int w = graph[u][i].second;
                    if (w == choose && res[v] == -1 && w <= c) {
                        res[v] = res[u] + 1;
                        q.emplace(v, w);
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            printf ("%d ", res[i]);
        }
        printf ("\n");
    }
    
    return 0;
}