#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
//#define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define all1(i) begin(i),end(i)
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug true
#define debug2 false


long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

void solve(){
    
    ll X,Y,P,Q;
    cin >> X >> Y >> P >> Q;
    
    ll x,y,g;
    g = extGCD(2*X+2*Y,P+Q,x,y);
    //これでx,yは(2X+2Y)x+(P+Q)y=gを満たす
    
    x%=(P+Q);
    x+=(P+Q);
    x%=(P+Q);
    //0<=x<P+Qにしたい　残りはyに押し付ける
    
    ll Ans = INF;
    REP(j,Y){
        REP(k,Q){
            //欲しいのは(2X+2Y)a+X+j = (P+Q)b+P+kをみたすa
            //(2X+2Y)a-(P+Q)b = P+k-X-jになる
            //(2X+2Y)a = P+k-X-j (mod P+Q)を満たすaが欲しい
            //さっき(2X+2Y)x=g (mod P+Q)を満たすxを求めた
            ll q = P-X-j+k;
            q%=(P+Q);
            q+=(P+Q);
            q%=(P+Q);
            
            
            if(q%g!=0)continue;
            ll r = q/g;
            //cout << "! " << q << " " << g << endl;
            ll a=(x*r)%((P+Q)/g);
            /*if(Q==8){
                cout << "! " << X+j MM P+k  MM q MM r MM a MM a*(2*X+2*Y)+X+j << endl;
            }*/
            Ans = min(Ans,a*(2*X+2*Y)+X+j);
            
        }
    }
    
    if(Ans==INF){
        cout << "infinity" << endl;
    }else{
        cout << Ans << endl;
    }
    
}

int main(void){
    
    ll T;
    cin >> T;
    REP(_,T){
        solve();
    }
    
    return 0;
}
// 2020-11-21 21:45:27
// clang-format off
#include <bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
// #include <atcoder/convolution>
// #include <atcoder/dsu>
// #include <atcoder/fenwicktree>
// #include <atcoder/lazysegtree>
// #include <atcoder/math>
// #include <atcoder/maxflow>
// #include <atcoder/mincostflow>
// #include <atcoder/modint>
// #include <atcoder/scc>
// #include <atcoder/segtree>
// #include <atcoder/string>
// #include <atcoder/twosat>
// #include <atcoder/all>
// using namespace atcoder;

// clang-format on
const int MX = 100010;
int n, m;
int visited[MX], color[MX];
vector<P> G[MX];  // v c
void dfs(int u) {
  for (auto [v, c] : G[u]) {
    if (visited[v]) continue;
    visited[v] = 1;
    int nc = 0;
    if (color[u] == c)
      nc = (c + 1) % n;
    else
      nc = c;
    color[v] = nc;
    dfs(v);
  }
}
void answer() {
  cin >> n >> m;
  rep(i, m) {
    int u, v, c;
    cin >> u >> v >> c;
    u--;
    v--;
    c--;
    G[u].emplace_back(v, c);
    G[v].emplace_back(u, c);
  }
  memset(color, -1, sizeof color);
  memset(visited, 0, sizeof visited);
  visited[0] = 1;
  color[0] = 0;
  dfs(0);
  rep(i, n) cout << color[i] + 1 << '\n';
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}