#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <memory>
#include <queue>
#include <string>
#include <utility>
#include <vector>

namespace {
using std::cin;
using std::cout;
using std::int64_t;
using std::size_t;
using std::uint32_t;

namespace base {
template <typename T, size_t... sizes>
struct NestedArray {};

template <typename T, size_t size, size_t... sizes>
struct NestedArray<T, size, sizes...> {
  using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};

template <typename T>
struct NestedArray<T> {
  using Type = T;
};

template <typename T, size_t... sizes>
using Array = typename NestedArray<T, sizes...>::Type;

void OptimizeIO() {
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
}

void OptimizeIO(const std::string &input_file, const std::string &output_file) {
  static std::ifstream input_stream(input_file);
  static std::ofstream output_stream(output_file);
  cin.rdbuf(input_stream.rdbuf()), cout.rdbuf(output_stream.rdbuf());
  cin.tie(nullptr), cout.tie(nullptr);
}
}  // namespace base

using base::Array;

const int kMaxN = 1.0e5 + 5, kMaxM = 3.0e5 + 5, kMaxW = 5.0e4 + 5,
          kMaxLogW = 17, kMaxK = kMaxN * kMaxLogW, kInf = 1.0e9 + 5;
const uint32_t kBase = 19260817;
int n, m, max_w;
Array<int, kMaxN> pre, w, dis;
Array<uint32_t, kMaxW> pow_base;
Array<bool, kMaxN> vis;
Array<std::vector<std::pair<int, int>>, kMaxN> edge;
std::priority_queue<std::pair<int, int>> q;

class PersistentSegmentTree {
 public:
  void set_n(int n) { n_ = n; }

  void Clear() {
    std::fill_n(rt_.begin() + 1, n, 0);
    std::fill_n(lc_.begin() + 1, tot_, 0);
    std::fill_n(rc_.begin() + 1, tot_, 0);
    std::fill_n(cnt_.begin() + 1, tot_, 0);
    std::fill_n(hash_.begin() + 1, tot_, 0);
    tot_ = 0;
  }

  void Insert(int p, int q, int x) { rc_[q] = Insert(rt_[p], 1, n_, x); }

  bool Cmp(int p, int q, int x, int y) {
    return Cmp(rt_[p], rt_[q], 1, n_, x, y) == -1;
  }

 private:
  int Insert(int p, int l, int r, int x);
  int Cmp(int p, int q, int l, int r, int x, int y);
  int n_, tot_;
  Array<int, kMaxN> rt_;
  Array<int, kMaxK> lc_, rc_, cnt_;
  Array<uint32_t, kMaxK> hash_;
};

int PersistentSegmentTree::Insert(int p, int l, int r, int x) {
  int q = ++tot_;
  hash_[q] = hash_[p] + pow_base[x], cnt_[q] = cnt_[p] + 1;
  if (l == r) return q;
  int mid = (l + r) >> 1;

  if (x <= mid) {
    lc_[q] = Insert(lc_[p], l, mid, x), rc_[q] = rc_[p];
  } else {
    lc_[q] = lc_[p], rc_[q] = Insert(rc_[p], mid + 1, r, x);
  }

  return q;
}

int PersistentSegmentTree::Cmp(int p, int q, int l, int r, int x, int y) {
  uint32_t hash_p = hash_[p], hash_q = hash_[q];
  if (x >= l && x <= r) hash_p += pow_base[x];
  if (y >= l && y <= r) hash_q += pow_base[y];
  if (hash_p == hash_q) return 0;
  if (l == r) return cnt_[p] < cnt_[q] ? -1 : 1;
  int mid = (l + r) >> 1, ans = Cmp(rc_[p], rc_[q], mid + 1, r, x, y);
  if (ans == 0) ans = Cmp(lc_[p], lc_[q], l, mid, x, y);
  return ans;
}

PersistentSegmentTree persistent_segment_tree;

void InitPowBase() {
  pow_base[0] = 1;
  for (int i = 1; i <= max_w; ++i) pow_base[i] = pow_base[i - 1] * kBase;
}

void Dijkstra() {
  persistent_segment_tree.set_n(max_w);
  persistent_segment_tree.Clear();
  pre[1] = 0;
  std::fill_n(dis.begin() + 1, n, kInf), dis[1] = 0;
  std::fill_n(vis.begin() + 1, n, false);
  q.emplace(0, 1);

  while (!q.empty()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    if (u != 1) persistent_segment_tree.Insert(pre[u], u, w[u]);

    for (const auto &e : edge[u]) {
      int v = e.first, w = e.second;

      if (dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w, q.emplace(-dis[v], v), pre[v] = u, ::w[v] = w;
      } else if (dis[u] + w == dis[v] &&
                 persistent_segment_tree.Cmp(pre[v], u, ::w[v], w)) {
        pre[v] = u, ::w[v] = w;
      }
    }
  }
}

void Print() {
  std::vector<int> path;
  for (int i = n; i; i = pre[i]) path.emplace_back(i);
  cout << path.size() << "\n";
  for (int i = path.size() - 1; i >= 0; --i) cout << path[i] << " ";
  cout << "\n";
}

void Solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) edge[i].clear();
  max_w = 0;

  while (m--) {
    int u, v, w;
    cin >> u >> v >> w, max_w = std::max(max_w, w);
    edge[u].emplace_back(v, w), edge[v].emplace_back(u, w);
  }

  InitPowBase();
  Dijkstra();
  Print();
}

int Main() {
  base::OptimizeIO();
  int t;
  cin >> t;
  while (t--) Solve();
  return 0;
}
}  // namespace

int main() { return Main(); }