//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

typedef long long ll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    std::sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(std::unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    std::reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

using namespace std;

const int MAXN = 1e5 + 228;

vector<pair<int, int>> g[MAXN];
vector<pair<int,int>> ng[MAXN];

vector<int> usd(MAXN, false), nxt(MAXN, -1);

vector<int> dp[MAXN];

void dfs(int v = 1) {
    for (auto &[to, w] : ng[v]) {
        dfs(to);
    }
    for (auto &[to, w] : ng[v]) {
        vector<int> cur = dp[to];
        vector<int> ncur;
        if (!cur.empty() && w > cur[0]) {
            cur.insert(cur.begin(), w);
        } else if (!cur.empty()) {
            for (int i = 0; i < cur.size(); ++i) {
                ncur.push_back(cur[i]);
                if (i == cur.size() - 1 || cur[i] >= w && w >= cur[i + 1]) {
                    ncur.push_back(w);
                }
            }
            swap(cur, ncur);
        } else {
            cur = {w};
        }
        if (cur > dp[v]) {
            dp[v] = cur;
            nxt[v] = to;
        }
    }
}

int32_t main() {
    std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    ll t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            g[i].clear(), ng[i].clear();
        }
        while (m--) {
            int x, y, w;
            cin >> x >> y >> w;
            g[x].emplace_back(y, w);
            g[y].emplace_back(x, w);
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
        q.emplace(0, 1);
        vector<int> d(n + 1, INT_MAX);
        d[1] = 0;
        while (!q.empty()) {
            auto [curd, v] = q.top();
            q.pop();
            for (auto &[to, w] : g[v]) {
                if (d[v] + w < d[to]) {
                    d[to] = d[v] + w;
                    q.emplace(d[to], to);
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            nxt[i] = -1;
            for (auto &[to, w] : g[i]) {
                if (d[to] == d[i] + w) {
                    ng[i].push_back({to, w});
                }
            }
        }
        dfs();
        int nw = 1;
        cout << dp[1].size() + 1 << '\n';
        for (int i = 0; i < dp[1].size(); ++i) {
            cout << nw << ' ';
            nw = nxt[nw];
        }
        cout << n;
        cout << '\n';
    }
}