#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

vector<long> dijkstra(int src, const vector<vector<pair<int, int>>>& graph) {
    int n = sz(graph);
    vector<long> dist(n, 1e18);
    min_pq<pair<long, int>> pq;
    auto push = [&](int u, long d) -> void {
        if (d < dist[u]) {
            dist[u] = d;
            pq.emplace(d, u);
        }
    };
    push(src, 0);
    while (sz(pq)) {
        auto [d, u] = pq.top();
        pq.pop();
        for (auto& [v, w] : graph[u]) {
            push(v, d + w);
        }
    }
    return dist;
}

vector<vector<pair<int, int>>> filter_sp(int n,
                                         const vector<long>& dist,
                                         vector<vector<pair<int, int>>> graph) {
    for (int i = 0; i < n; i++) {
        auto& a = graph[i];
        a.erase(remove_if(begin(a), end(a),
                          [&](const auto& e) -> bool {
                              auto& [v, w] = e;
                              return dist[i] + w != dist[v];
                          }),
                a.end());
    }
    return graph;
}

struct S {
    static constexpr int bsize = 250;

    array<uint16_t, bsize> small {};
    basic_string<uint16_t> large;

    void clear() {
        large.clear();
    }

    void insert(int x) {
        if (x < bsize) {
            small[bsize - x - 1]++;
        } else {
            large.insert(upper_bound(begin(large), end(large), x, greater<>()), x);
        }
    }

    bool operator<(const S& s) const {
        if (large == s.large) {
            return small < s.small;
        }
        return large < s.large;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
    auto dist = dijkstra(0, graph);
    graph = filter_sp(n, dist, graph);
    int ord[n];
    iota(ord, ord + n, 0);
    sort(ord, ord + n, [&](int a, int b) -> bool {
        return dist[a] < dist[b];
    });
    S dp[n];
    int from[n];
    for (auto& a : ord) {
        for (auto& [v, w] : graph[a]) {
            auto tmp = dp[a];
            tmp.insert(w);
            if (dp[v] < tmp) {
                dp[v] = tmp;
                from[v] = a;
            }
        }
        dp[a].clear();
    }
    vector<int> ans;
    int u = n - 1;
    while (true) {
        ans.push_back(u);
        if (!u) {
            break;
        }
        u = from[u];
    }
    reverse(begin(ans), end(ans));
    cout << sz(ans) << endl;
    for (int i = 0; i < sz(ans); i++) {
        cout << ans[i] + 1 << " \n"[i == sz(ans) - 1];
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    int tcs;
    cin >> tcs;
    while (tcs--) {
        solve();
    }
}