/*
#############################################################################################%####################################%###############
#--%###*-=+-####--+::::=##%-:*#=:%#*-*#%-::+########%=::+##:=%#*-=#=-##:::::+%-:###-=####-:::=%##-::::*##=:=#####-::*%::::::+#-+###-::*##%--#%%--#
#::%###*:-*:-##=:#=..::-###=.*#-.*#=:**:.:..:#####*#:.:::##.-##+.+#=:##...::+%:.=#%:-####:.::.:%#..:::*#%::.####-.::-%:....:+*:=#*..:.:=##:.=##:-#
#::####*:-%::%#-:%=.#######*.+#:.:%:.%-:*##+:+#####-:#%##*#.-##+:=#=:*#.:%###%::.*%:-###%::##=:*#.-#####+:#.+##::####*##-:%##*.=#-:##%-:#%::.##::#
#::####*:-#+:*#:=#=.::-*####:=*.=:#:-#::%##*.=#####::######.::::.=#=:##..:--#%::--#:-####:.##::##.::-=##-:#:=#+:=#######-:%##*.=%:-###+.=%::-:#::#
#::####+:-#*:+*.*#=:::-#####:-=:+.*.+%::##%*.=*--=#::#####*..::..=#=:*#..::-#%:.+.+:-####:..:.+##:::-=##:=#-:*+:=#######::###*.=#:-###+:-#::*.*.-#
#::%###+:-##:-::%#=:########:::-#:-:%#::*##*.+#--=#::*###*#:-##+:=#=:*#::%###%::%=.:-####:.#::*##:-####*.....#*:-#######-:###*:=%-:###=:+%::#-.::%
#::*****:-##-..+##=.+***####=..##..:##*::%+.:####*#+::#*:##.-##*:=#=:##.:*#**%::#*:.-###%:.##:-##.:***#::###.-%-:-#+-%##-:###*:=#+..#+.-%#::#%:.:#
#:..::+*:=##%::*##=:...:%##%#::##=:-###*:..:#########:::-#*:-##*:+%=:##:..::=%::##+:-###%-:#%=:=%:....+:-###--*#=:.:=###-:###*:+*#*.::-###:-##+:-#
################################################################################################################################################%#
####################################################%#################################################################%#########%#################
%#%#%@%@@%%%%%*%@%#%%%%@@%@@@@@@#%%#***+++@@@@@@@@@@*@@%@@@@@@%#--@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:*@@@@@@@%@@@@@@@@
##%%%@#@@@%%%%###@%%#%@@@@%#@@@@+%%++*%=##%@@@@@@@@@@-#@@@%@@@%#=:@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:*@@@@@@%%=@@@@@@@
-#@@@@%%%%#%%%@%#####%##%#%*##+*+#@#*%%%+%%###@@@@@@@@+.-%@@@@%#-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:+@@@@@@=:@@@@@@@@
--#@@#*%@@@@@@%%@%%#%%%***%@%##*++#+%%%%*=**#%@@@@@@@@@%+:.:-=*#%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:@@@@-.:@@@@@@@@@
:-:*%@@%%%@@%@%%%@#%*%*#%###%%%##*%#**=*+=-+=#=**@@%%*++#@@*=::.:.:::.:-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@%%=-::-%@@@%@@@@@@
+--:*@@@@@@@@@@@@@@@@@%#%#%#%%%%%%#**+++=+**%#=-%%#*+++=%@**%@@@%%+-....::=@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::.-#@@@@@@@@@@@@@
%+:::+@@@@@@@@@@@@@@@%@%#*#%@%*+*%@%@#*+*%%#%%@%%#++*+=#@%*@%@#-=#++*%%-...:#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@+:::::*%#-@@@@@@@@@@@@@@
#%##%%%@@@@@@@@@@@@@@@%@@@@@@%#%%@@%%@#+%%@*+##%%%#*@+*@%@@@@%#::=+++++*%:.::#@@@@@@@@@@@@%=#@@@@@@@@@@@@@@+@#@@@@@@@@@@%+::.+@*#%-:@@@@%@@@@@@@@@
%%%###%%%%###%%%@@@@@@@@%%@%%%#@%%@@@@%%@#%%=*#=++*%%%*@+#@%%@#-::%*%#*=+%=:..%@@@@@@@@@@@%==-=#@%@@@@@@%===*@@@@@@@@@%@#::-%#*+%%:+@@@@@@@@@@@@@@
%#%%##%#%@%#%%%%#%@@@@@%%%@@%%%%@%@%@@@@%@%#*=*=*##*#%%+*@@#*#%#::-#===:-+@:.:*@@@@@@@@@@@%+---==*@@%@@*==--=@@@@@@@@@@%*::%+-:*@+:%@@@@@@@@@@@@@@
%%#%%%###%%%#%###%@#=+=%@@%%@@%@%%@@@@%%%%@@@%@@%#+%###*%%@%@#%#+:.=@#%#**@::.*@@@@@@@@@@@%#=-=-===*@%*-=====#@@@@@@@@@#=:*###%@#:-@@@@@@@@@@@@@@@
%#@#%%%%%%%%%##%#%#@*+++%%@@@@@@#*@@@@@%@@@@@#%@@@**@%*%%@@@@#%@#+:::%*+++@=:.#@@@@@@@@@@@@#*==---=-*#*-==-=-=@@@@@@@@%#::@+*%%-.-@%@@@@@@@@@@@@@@
%##%%%%%%#%%#%%#%#%#@*+++@@%@@@@@@@@@@@@@@@@@@@@%%#%@%@%@@@%*#%#@%*:::=@+*@+::@@@@@@@@@@@%%@%#+==-===@*===-=*@@@%@@@@@#*:+%#+:.:#@%@@@@@@@@@@@@@@@
%##%%%%%###%#%%#%#%#%%*+*+%@@@@@@@@@@@@@@@@@@@@@@@%#@@@@@@@%@%%%#%@%+:.:-#@*::@@@@@@@%%%%%%%%@%#*=--=@*--=##*#@@@@@@@##=:*:-=#%#@@@@@@@@@@@@@@@@@@
##%%#%%%%@%%@%%@%%@@%%@*+*=%@@@@@@%@@@@@@@@@@@@@@@%@@@@@@@@@%@###@%%@%*::-@#=.%@@@@%%##%%%###%%%@%*+=@==#*+*%*++#@@@%#+.=@@*##+++%%@@@@%%%%%%%%%%%
#%#%%%@#%%%%#%%@###%#%%%++*+#@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@%%%%@**@@@%*%%#:+@@%%#%#*++##%#+++++*%%%*++++++*@%@@@##=.-%@%%#%++++@@@@%%%%%%%%%%%%
%@%#%#@%%@%%%%%%%%%%#%%@%%%#=*@@@@@@@@@@@@@@@%@@@@%@@@@@@@@@@@%#%%%#@@@%@%@@##:-%%#*+*#%%%*+++++++++++*++++++++%%##=:.*@@@#%%#++++@@@%%%######%%%%
#%%%%@%%%%#%%%@@@@@%%%%%%%%%@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#%@@%@@%#%%#%%*%@##*-:=+*%%%#*++++++++++++*+++++++++#+:+#@@@@@@@@%*+++@@@%%%##########
%%%%@@@@%%%%%#%#%##%%%%%%#%%%#+==***%@@@@@@@@@@@@@@@@@@@@@@@@@@@@***##*#%%%%%%@%%%#*#@%*+++++++++++++++%++++++++=#*++%@@%@@@@%*+++@@%%%%##########
@@@%%%#%%###%%%%%#######%%%%%##+==#=====*+#%@@@@@@@@@@@@@@%@@@@+*#*+=#%@%#%%%%%%#%%%%%*+++++++**+++++++**+++**++++@+++%%@@@@@@#+=%%%%%%%##########
####%%%%%#%%%%%#%@%#####%%%%%%%*=+=#=====#+==*@@@@@@@@@@@**@@@###%@%%@@#%%%%%%%%##%%@*++++++*%++++++++++*++++###*+#*++*@@@@@%%%*@%%%%%%###########
%##%%%%%%##%%%%##%%######%%#%%%#++=+%=====#===+%@@%%@@@@@%#@@@%%%%%@@%#%%%%%%%%%%%%%%++=++#%#*++++++++++*+++++#==##++++@%@@%%%%####%%##%%######*##
%####%@%#%#%%%%###@%####%###%%%%#====*=====#==++#@@@@@@@@@@@@@@#%%%@%#%%%%%%%%%####%%#%%*===*#++++++++++*+++++#===+%+++%%%%%%%%%%#####%%%%%%%%%%%%
%####%#%#%#%%%%###%@######%%%%%%%+===#+====+%+=+*%@@@@@@@@%%#*%%@@@%%%%#%#%%%%%#++*#%=---==-=+%*++++++++++++++#=====%++*%%%%%%%%%#%###%%%%%%%%%%%@
%######%%%%%%%#%##%%%%%####%%%%%%#++==#======#=++*%@@@@@@@@@@%%@@@%%##%#%%%%##*++++#*-===---=-==##++++++++++**==-===%++#%%%%%%%%%%%%%#%%%%%%%@@@@@
%####%%#%%%%###%%%#%%%#%###%@%%%%%++=++#=====**=+++%@@@@@@@@@@@@@##%#%%%%%%#%*+++++%+==-===--===-=*%*+++++#*==-=--==%++#%%%%%%%%%%%%%%%#*%@@@@@@@@
%#######%@%%@@@%%#%%%%#%%#%%%%%%%##+*==**==+==*==+*+@@@@@@@@@@@@%%%%#%%%%%%#+++++++%+=========--====+%%**-=--====-==%++#@@%@%%%%#*%%%%%#%**+*@%@@%
%%#%%#%%#%@#****#%@@@@@%%@@@@@@@@@@@@@@@@%%#***+*++++%@@@@@@@@@%%%%%%%#%%%%*+++++++%+===-==========--====---=====-=+%++#@@@%%+++###%#%-=+#=-#%@@@#
%%##%%%#%##@##*******##%%%%%%#####**#**#*****##%@@%%%#@@@@@@@@%%%%%%%%%#%#*++++++++##=-====---=---==--==--=======-=*#++@@%#=*+++--:-=-+-==#*=++*=-
#%##%%%####%@%#%%%%%%%%%%%#***********************#%@@@@@@@@@@%%%%%%##%##*++++++++++%=---=--===--===========-==-==-%#+*@#**%#%%%@#*%%%%%#%@@%-*==*
%@#********##%%%%%%%%%%%##****************************%@@@@@@%#%%%%%#%%%*+++++++++++*%*-=-=-=-+%=-===========-*#==-%*=%+==%%%%%@@@##@%%@@@@@%@%%%%
%%%%%%%%%%%%%%%%%%%%%%%#********************************#%@@@%##%#%%#%%*+++++++++++*++#%==--=%*%============--%%=-*#+%%%%%%%@@@@%@%@@@@@@@@@%@@@%@
%%%%%%%%%%%%%%%%%%%%%%%#*******************************##%%%%#%%%%%%%%*++++++++=+#@#+++%%=-+#+*%====-=----===-##*#++++%%%%%@%%%@@@@@@@@@@@@@@@@@@@
%%%%%%%%%%%#@%%%%%%%%%%###****************************#%%%#%#%%%%%%%%#++++++++#@%###++**###++++##-====--=====#**%*++++*@@@%##%@@@@@@@@@@@@@@@@@@@@
%%%%@%*++++++%%%%%%%%%%%%%####*************####%%#%#**#%###%%%#%%%%%#+++*#%@%#*+++#%+%++++++++++#%==-===--=+%+++++++#==#%%%%@@@@@@@@@@@@@@@@@@@@@@
%%@#+=+++++++*%@@@%%*+++*@%%%%%%%%%##%%%@@%%%#++==**+%#########%%@%%%#%%%%#%*+++++***=+++++++++++*%#===-==@*++++++++*%++%%@@@@@@@@@@@@@@@@@@@@@@@@
@#+=+++++++++++++++=++++++%%%%%%%%%%%%%%###%#%*====##%##########%%%%%#%###%#+++=*++++++++++++++++++#@*-+%*+=+++++++++@++#@@@@@@@@@@@@@@@@@@@@@@@@@
#+++++++++++++++++++++++++%%%%%@@@%##%%@#%%%%##+=*%##########%#@%%%%%%%%%%%++++#++++++++++++++++++++++#++++++++++++++*#++@@@@@@@@@@@@@@@@@@@@@@@@@
#+++++*++++%++++++++++++++#@%@%%%#%##%%%%%%#%#%#%##############@%%%%%%%%%#++++*=++=+++++++++++++++++++*+++++++++++++++%++%@@@@@@@@@@@@@@@%%@%@@@@@
##%%%#++++#=++++++#+++++++*%#%%@%#######%#%%#%%%###%##########%#%%%%%@%#%*+++**=+++++++++++++++++++=++#+++++++++++++++%++#@%@@@@@@@@@@@@@@@@@%@%%#
%%%%%++++%+++++++*@%#+=+++*%%%#%@#%%###%%@%#%%##############%%%%%%#%@%#%*++++*++++++++++++++++++++++++#+++++++++++++++#*+#@@@@@@@@@@%%#########%%%
%%%@%*++*++++++++#@%@%####@%%%#%%@#%####%#%%%#%##############%%%%%%%@%%%++++*+++++++++++++++++++++++++#++++++++=++++++#%%@###*###%%%%%@@@@@@@@@@@@
%%%@##++*+++++++*%@%%@@%%%@%%##%%%%##%%%#%%%%################%%#%%#@%%%#+++++=++++++++++++++++++++++++#+++++++*+++++++#%%%@%%%%#%%@%#%@@@@@@@@@@@@
%%%@%##+*++++++#%@%%##@%%%%##%%%#%@%#%#%#%%#################%@%%#+=*##%%*++++++++++++++=+++++++++++=+=#+++++++*+++++++#@%%%%##%@@@@@@@@@@@@@@@@@@@
%%%%@%##**++##%%%##%##%@%%#%#%%##%#@%#%%%#############%######+--====%%#%#+++++++++++++*+++++++++++++++#++++++**+++++++##***#%#%@@@@@@@@@@@@@@@@@@@
%%%%%@%#%##%##%%##%#%%%%%#%%#%%%%%##@%#@%########%###%@#####==-======@%%#+++++++++++++#=++++++++++++#=*%+++++#++++++++%#*#%@@@%@@@@@%@@%%@@%%@@@@@
%%%%%%@%#%%%%@%##%%#%%%%%@%##%%%%%%%%%%%###########@%#%####=--=-=-=*%#@#%*++++++++++++@*++++++++++*+==-=##+++@*+++++++%%@%%@@@@@@@%%@%%%%%%@@@@@@@
%%%%%%%@%#%@%#%%%#%%##%%##@%#%%%%%#%#%%#%###%###%@###%%###=======+@*+=#@%%+++++++++++%*%+++++++=*#-=--====@+*+%+++++++%@@@@%%%%%%%%%%@@%@@@@@@@@@@
%%%%@%%#%%%%@%%%%%%%######%%%##%%#%%#@%######@@######%%%#=-=--=%%#+-===*@%#++++++++%+==#*++++=*%=-======-====-+%*+++++@%%%@@@%%%%%@%%@@@@@@@@@@@@@
@@#####%###%#%#%%%%%####%##%@%#%%%@%#%%%%%%##########%%*=-==#@#%==-=-==-+%@+++++##===-==@+++#*==-=======-==--===%#+++##@@@@%%%%%%%%%@@@@@@@@@@@@@@
%###%%%%##%%%#@%%%%%%%%##%#%%@%@%#%##%###############%#%%##%#*---=-==--===*%###==-====-=+%%=----=-=====--===-==-=%%++@=%@%%%%%%%%%@@@@@%@@@@@@@@@@
%%%############@#%#%%%%#%#%#%@%#%###########################==-======--======-===--===--===--==========-----======#%%-=+%%%@@%%%@@@@@@@@@@@@@@@@@@
%%%%%#########%#%#%%%%%%%#@@###############################*=====-------=--==--==---==-=====-============-=-=======---==%@@%%%%%%@@@@@@@@@@@@@@@@@
%%%%%##########%#@#%%#%%@%##%##########################%###==-=====------======-=-=----=-#=====-===-=--=====--=--======-@@@@@@@@@@@@@@@@@@@@@@@@@@
%%%%%#########%%##%%%#%%##################################*========------=======+===---=#%==---=-==@==-===-*==-=-======-%@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%#########%##%%%#@################################%###=-==========---=-====*%===-==*%%==-==-==@#%-=--==%+-===-====--#@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%########%#%#@%################%##################%*=====-===-===--=-==-#%%--=-=*##%+-=====@*#%@---==%%-==--=====-*@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%%########%#@###################################%##=-======-%====--=-==%#%+=-=-@#*%%*-=--+%*++##%*-==%%%---=----=-*@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%%########%###############%@%%##%#################*-========@%+==-==-*@+%@=-=%%*++%%#==*%#++=++%%%%*@#%%#--======-*@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%%######%%%############%@%#%#@####################=-=======+##@*-==@@**=%%###*+=++##%%%#*+++++++*#%%*+###@+=====-=%@@@@@@@@@@@@@@@@@@@@@@@@@
*/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;

int g;
bool twoColorable;

void dfs(int x, int y, vector<vector<array<int, 2>>>& adj, vector<array<bool, 2>>& seen) {
    seen[x][y] = true;
    if(seen[x][y ^ 1]) {
        twoColorable = false;
    }
    for(array<int, 2> i : adj[x]) {
        if(!seen[i[0]][y ^ ((i[1] / g) % 2)]) {
            dfs(i[0], y ^ ((i[1] / g) % 2), adj, seen);
        }
    }
}

int n; int m; int k; int s; int t;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T; cin >> T;
    for(int test = 1; test <= T; test++) {
        cin >> n >> m >> k >> s >> t;
        vector<vector<array<int, 2>>> adj(n);
        g = k;
        for(int i = 0; i < m; i++) {
            int u; int v; int w;
            cin >> u >> v >> w;
            u--; v--;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
            g = __gcd(g, w);
        }
        if((k / g) % 2) {
            cout << k / g << "\n";
            continue;
        }
        vector<array<bool, 2>> seen(n, {false, false});
        twoColorable = true;
        dfs(s - 1, 0, adj, seen);
        cout << max((twoColorable ? k / g / 2 : k / g), 1) << "\n";
    }
}