// In the name of God.
// Ya Ali!

#include <bits/stdc++.h>
//#define int long long 
using namespace std;

const int maxn = 1e3 + 17;
int n, m, t, nex[maxn], bak[maxn], v[maxn], u[maxn], w[maxn];
bool inf[maxn][2];
void solve(){
	memset(nex, 0, sizeof nex);
	memset(bak, 0, sizeof bak);
	memset(inf, 0, sizeof inf);
	static int TN = 0;
	TN++;
	if(!(cin >> n >> m)){
		cout << TN << '\n';
		exit(0);
	}
	for(int i = 0; i < m; i++){
		cin >> v[i] >> u[i] >> w[i];
		v[i]--, u[i]--;
	}
	for(int t = 1; t <= n; t++)
		for(int i = 0; i < m; i++)
			if(nex[ v[i] ] > nex[ u[i] ] + w[i]){
				nex[ v[i] ] = nex[ u[i] ] + w[i];
				inf[ v[i] ][0] |= t >= n;
			}
	for(int t = 1; t <= n; t++)
		for(int i = 0; i < m; i++)
			if(bak[ u[i] ] > bak[ v[i] ] + w[i]){
				bak[ u[i] ] = bak[ v[i] ] + w[i];
				inf[ u[i] ][1] |= t >= n;
			}
	for(int t = 1; t <= n; t++)
		for(int i = 0; i < m; i++){
			inf[ v[i] ][0] |= inf[ u[i] ][0];
			inf[ u[i] ][1] |= inf[ v[i] ][1];
		}
	for(int i = 0; i < n; i++)
		if(inf[i][0] || inf[i][1])
			cout << "INF" << '\n';
		else
			cout << bak[i] + nex[i] << '\n';
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	int t;
	cin >> t;
	while(t--)
		solve();
}