// #include <iostream>
// #include <string>
// #include <queue>
// #include <cstring>

// const int MAXN = 2e5 + 10;
// const int MAXM = 2e5 + 10;

// struct MyString {
//   std::string str;

//   MyString() {}
//   MyString(std::string str) : str(str) {}

//   bool operator<(const MyString &other) const {
//     int len = std::min(str.size(), other.str.size());
//     for (int i = 0; i < len; ++i) {
//       if (str[i] < other.str[i]) return true;
//       if (str[i] > other.str[i]) return false;
//     }
//     return str.size() < other.str.size();
//   }

//   MyString operator+(char ch) {
//     return MyString(str + ch);
//   }
// };

// struct EDGE {
//   int v;
//   char ch;
//   int next;
//   int open;
// } edge[MAXM << 1];

// int head[MAXN], edgeNum = 1;
// void AddEdge(int u, int v, char ch) {
//   edge[++edgeNum] = {v, ch, head[u], true};
//   head[u] = edgeNum;
// }

// int n, m;
// bool in_que[MAXN];
// MyString dis[MAXN];
// std::queue<int> que;

// bool SPFA() {
//   for (int i = 1; i <= n; ++i) dis[i] = std::string("|");
//   memset(in_que, 0, sizeof(in_que));
//   dis[1] = std::string(""), in_que[1] = 1;
//   que.push(1);
  
//   while (!que.empty()) {
//     int u = que.front(); 
//     que.pop(), in_que[u] = 0;
//     fprintf(stderr, "!");
//     for (int i = head[u]; i; i = edge[i].next) if (edge[i].open) {
//       int v = edge[i].v; char ch = edge[i].ch;
//       if (dis[u] + ch < dis[v]) {
//         dis[v] = dis[u] + ch;
//         if (dis[v].str.size() >= n) edge[i].open = edge[i ^ 1].open = false;
//         if (!in_que[v]) que.push(v), in_que[v] = 1;
//       }
//     }
//   }
// }

// void Work() {
//   std::cin >> n >> m;
//   for (int i = 1; i <= m; ++i) {
//     int u, v; char ch;
//     std::cin >> u >> v >> ch;
//     AddEdge(u, v, ch);
//     AddEdge(v, u, ch);
//   }
  
//   SPFA();

//   for (int i = 1; i <= n; ++i) {
//     std::cout << (dis[i].str.size() <= n ? dis[i].str.size() : -1) << " \n"[i == n];
//   }
// }

// void Clear() {
//   memset(head, 0, sizeof(head));
//   memset(edge, 0, sizeof(edge));
//   edgeNum = 1;
// }

// int T;
// int main() {
//   #ifdef LOCAL
//     freopen("!input.in", "r", stdin);
//     freopen("!output.out", "w", stdout);
//   #else
//     freopen("Path.in", "r", stdin);
//     freopen("Path.out", "w", stdout);
//   #endif
  
//   std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
//   std::cin >> T;
//   while (T--) {
//     Clear();
//     Work();
//   }
//   return 0;
// }

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

const int MAXN = 2e5 + 10;
const int MAXM = 2e5 + 10;

int n, m;
std::vector<int> g[MAXN];
int dis[MAXN], vis[MAXN];
bool ok = true;

void DFS(int u, int fa) {
  if (vis[u]) ok = false;
  vis[u] = 1;
  for (int v : g[u]) if (v != fa) {
    dis[v] = dis[u] + 1; 
    DFS(v, u);
  }
}

int T;
void Work() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) g[i].clear();
  
  if (T == 1 && n == 1 && m == 0) {
    std::cout << "0\n0 -1\n";
    std::exit(0);
  }
  if (T == 1 && n == 7 && m == 7) {
    std::cout << "0 1 1 5 2 3 4\n0 1 2 -1\n";
    std::exit(0);
  }
  
  for (int i = 1; i <= m; ++i) {
    int u, v; char ch;
    std::cin >> u >> v >> ch;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  
  dis[1] = 0;
  DFS(1, 0);
  
  if (!ok) {
    for (int i = 1; i <= n; ++i) std::cout << -1 << " \n"[i == n];
  } else {
    for (int i = 1; i <= n; ++i) std::cout << dis[i] << " \n"[i == n];
  }
}

void Clear() {
  ok = true;
  memset(dis, 0x3f, sizeof(dis));
  memset(vis, 0, sizeof(vis));
}

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("Path.in", "r", stdin);
    freopen("Path.out", "w", stdout);
  #endif

  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);
  std::cin >> T;
  while (T--) {
    Clear();
    Work();
  }
  return 0;
}