#include <bits/stdc++.h>
#define INF 1000000007
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i < b; i++)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef long long int lli;

typedef vector<int> vi;
typedef unordered_map<int,int> umi ;
typedef unordered_set<int> usi ;
typedef pair<int,int> pi;
#include <bits/stdc++.h>
 
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
 
 
//declare here -------------------------------------------------------------
const int N =2e3+1 ;
vector<pair<int,int>> adj[N] ;
priority_queue<pi> q ;
int n,m ;
vi visited(n+1) ;
int mybfs(int x){
	visited.assign(n+1,0) ;
	//debug(visited) ;
	//debug(adj[x],x);
	q= priority_queue<pi>() ;
	for(auto X:adj[x]){
		q.push( MP(- X.F , X.S)) ;
	}
	while(!q.empty()){
		auto temp =q.top() ;
		q.pop() ;
		if(visited[temp.S]) continue ;
	    //debug(x,temp.S, temp.F) ;
		visited[temp.S] =true ;
		if(temp.S== x) return -temp.F ;
		for(auto X:adj[temp.S]){
			q.push({temp.F - X.F , X.S}) ;
		}
 	}
 	return -1 ;

}


// solve here --------------------------------------------------------------
 
void solve(){
	cin>>n>>m ;
	int u,v,w; 
	REP(i,0,m){
		cin>>u>>v>>w ;
		adj[u].PB(MP(w,v)) ;
	}
	REP(i,1,n+1){
		cout<<mybfs(i)<<"\n" ;
	}
}

 
 
 
//------------------------------------------------------------------
 
int main(){
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long test =1 ;
	//cin>>test ;
	while(test--){
		solve() ;
		cout<<"\n" ;
	}
	return 0 ;
}
#include <bits/stdc++.h>

const long long INF = 1e9;
const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long long LINF = 1e18;
using namespace std;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define COUT(x) cout<<(x)<<endl
#define SCOUT(x) cout<<(x)<<" "
#define VECCOUT(x) for(auto&youso_: (x) )cout<<right<<setw(10)<<youso_<<" ";cout<<endl
#define ENDL cout<<endl
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) long long __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define mp make_pair
#define PQ priority_queue<long long>
#define PQG priority_queue<long long,V,greater<long long>>


typedef long long ll;
typedef vector<long long> vl;
typedef vector<long long> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef pair<long long, long long> pll;


#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
template<class T>
void mod(T &x) {
    x %= MOD;
    x += MOD;
    x %= MOD;
}

ll GCD(ll a, ll b) {
    if(b == 0) return a;
    else return GCD(b, a%b);
}

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

void Main() {
    LCIN(T);
    for(int i = 0; i < T; i++) {
        LCIN(N, S, K);
//        cout << "–––––––––––––" << endl;            
        if((N - S)%GCD(N, K)) {
            cout << -1 << endl;
        } else {
            ll x, y;
            ll a = extGCD(K, N, x, y), b;
            S = N - S;
            ll s = S;
            ll M = ((S*y)%K - K)%K;
            ll tm = S*x - N*((M - S*y)/K);
//            cout << "N:" << N << endl;
//            cout << "S:" << S << endl;
//            cout << "K:" << K << endl;
//            cout << "M:" << M << endl;
//            cout << "x:" << x << endl;
//            cout << "y:" << y << endl;
//            cout << "a:" << a << endl;
            
            cout << tm/a << endl;
        }
    }
}

int main() {
    cout << fixed << setprecision(15);
    Main();
    return 0;
}