C_3

#include <iostream>
#include <map>
#include <string>
#include <fstream>
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

struct edge{
    int fr, to, w;
};

int main()
{
#ifdef _DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    const int INF = 2000000000;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    int T, n, m, v1, v2;
    cin >> T;
    vector<edge> g;
    for(int o = 0; o < T; o++){
        cin >> n >> m >> v1 >> v2; v1--, v2--;
        vector<int> w(n, -1);
        g.clear();
        for(int i = 0; i < m; i++){
            int u, v, w; scanf("%D%D%D", &u, &v, &w); u--, v--;
            edge e; e.fr = u, e.to = v, e.w = w;
            g.push_back(e);
        }

        vector<int> d(n, INF);
        d[v1] = 0;
        vector<pair<int, int>> p(n);
        for(int i = 0; i < n; i++)
            p[i] = make_pair(-1, 1);
        p[v1] = make_pair(v1, 1);

        vector<bool> used(n, false);
        for(int i = 0; i < n; i++){
            //bool up = false;
            for(int z = 0; z < m; z++){
                int to = g[z].to, from = g[z].fr; //cout << p[to].second << " " << g[z].w << endl;
                int aux = gcd(p[to].second, g[z].w); cout << aux << endl;
                if(aux == 1 && (p[to].second != 1 || g[z].w != 1) && d[to] > d[from] + g[z].w)
                    d[to] = d[from] + g[z].w, p[to] = make_pair(from, g[z].w);
            }
        }

        if(d[v2] <= INF / 2 + 100){
            vector<int> res;
            for(int i = v2; i != v1; i = p[i].first){
                res.push_back(i);
            }
            res.push_back(v1);
            reverse(res.begin(), res.end());
            cout << res.size() << " ";
            for(int i = 0; i < res.size(); i++)
                cout << res[i]+1 << " ";

            cout << endl;
        }
        else
            cout << -1 << endl;


        for(int i = 0; i < n; i++)
            cout << i+1 << " " << p[i].first+1 << " " << p[i].second << endl; cout << endl;

    }

    return 0;
}