#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

namespace std {
template <typename U, typename V>
ostream &operator<<(ostream &o, pair<U, V> p) {
  return o << '(' << p.first << ',' << p.second << ')';
}
}

constexpr int64_t kInf64 = 1LL << 60;

// 0-base
pair<vector<array<int, 3>>, vector<int>> shortest_dag(const auto &e, int s, int n) {

  vector<vector<pair<int,int>>> g(n);
  for (auto [x, y, w] : e) {
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }

  vector<int64_t> d(n, kInf64);

  vector<int> ord;
  priority_queue<pair<int64_t, int>> pq;
  pq.emplace(d[s] = 0, s);
  while (not pq.empty()) {
    auto [l, u] = pq.top();
    pq.pop();
    if (l == -d[u]) {
      for (auto [v, w] : g[u])
        if (d[u] + w < d[v])
          pq.emplace(-(d[v] = d[u] + w), v);
      ord.push_back(u);
    }
  }

  vector<array<int, 3>> ret;
  for (int i = 0; i < n; ++i) {
    for (auto [j, w] : g[i]) {
      if (d[i] + w == d[j])
        ret.push_back({i, j, w});
    }
  }
  return pair{ret, ord};
}

const int maxn = 100025;

struct List {
  using u16 = uint16_t;
  int sz;
  pair<u16, u16> e[320];
  List() : sz(0), e{} {}
  void add(u16 val, u16 rep = 1) {
    auto it = lower_bound(e, e + sz, pair<u16, u16>(val, -1U), greater<>());
    if (it < e + sz && it->first == val) {
      it->second += rep;
      return;
    }
    int j = it - e;
    for (int i = sz - 1; i >= j; i--)
      e[i + 1] = e[i];
    e[j] = {val, rep};
    ++sz;
  }
};

bool cmp(const List &a, const List &b) {
  for (int i = 0; i < a.sz && i < b.sz; i++) {
    if (a.e[i] != b.e[i]) {
      return a.e[i] > b.e[i];
    }
  }
  assert(a.sz == b.sz);
  return false;
}

List l[maxn / 4], cur, tmp;
int mapping[maxn];
int dep[maxn];
int pa[maxn], paw[maxn];

void solve() {
  int n, m;
  cin >> n >> m;

  vector<array<int, 3>> es(m);
  for (int i = 0; i < m; i++) {
    auto &[u, v, d] = es[i];
    cin >> u >> v >> d;
    --u, --v;
  }

  const int src = 0, dst = n - 1;
  auto [dag, ord] = shortest_dag(es, src, n);

  vector<vector<pair<int,int>>> g(n);
  for (auto [x, y, w] : dag) {
    debug(x+1, y+1, w);
    g[y].emplace_back(x, w);
  }


  const int lim = n / 4 + 1;

  for (int r = 0; r < 4; r++) {
    int tot = 0;

    for (int i = 0; i < n; i++)
      mapping[i] = -1;

    for (int x : ord) {
      if (x == src) {
        mapping[x] = tot++;
        debug(mapping[x], tot);
        l[mapping[x]] = List();
        dep[x] = 0;
        continue;
      }

      cur = List();
      cur.add(0, 50001);
      pa[x] = -1;

      auto GetList = [&](auto self, int z) {
        debug("GETLIST", z + 1);
        if (dep[z] % 4 == r || z == src) {
          debug(z);
          tmp = l[mapping[z]];
          return;
        }
        self(self, pa[z]);
        tmp.add(paw[z]);
      };

      for (auto [y, w] : g[x]) {
        GetList(GetList, y);
        //  debug(tmp.sz, cur.sz);
        //  orange(tmp.e, tmp.e + tmp.sz);
        //  debug(y+1, w);
        tmp.add(w);
        //  orange(tmp.e, tmp.e + tmp.sz);

        if (cmp(tmp, cur)) {
          cur = tmp;
          pa[x] = y;
          paw[x] = w;
        } else {
          debug(tmp.sz, cur.sz);
          orange(tmp.e, tmp.e + tmp.sz);
          assert(pa[x] != -1);
        }
      }

      assert(pa[x] != -1);

      debug(r);
      debug(x+1);
      orange(cur.e, cur.e + cur.sz);

      dep[x] = dep[pa[x]] + 1;
      if (dep[x] % 4 == r) {
        mapping[x] = tot++;
        if (tot > lim) {
          debug(x);
          orange(all(ord));
          orange(pa, pa + n);
          orange(dep, dep + n);
          debug("VIOLATED");
          break;
        }
        l[mapping[x]] = cur;
      }

      if (x == dst) {
        vector<int> v;
        // v.reserve(n);
        for (int i = x; i != src; i = pa[i]) {
          v.push_back(i);
        }
        v.push_back(src);
        reverse(all(v));

        cout << v.size() << '\n';
        for (size_t i = 0; i < v.size(); i++)
          cout << v[i] + 1 << (i+1==v.size() ? '\n' : ' ');
        return;
      }
    }
  }

  assert(false);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--)
    solve();

  return 0;
}